# Need Help Shifting Bits

I am going nuts today

I’m currently porting another 2D physics library, this one on a par with the complexity of Box2D. It will form the basis of a game I have in mind. It’ll be open sourced when done.

The library makes extensive use of Java’s `>>` and `>>>` operators and they have been driving me all day because I can’t seem to port them correctly to Xojo.

The `>>` operator is the signed right shift operator. That is, it shifts all bits in the integral passed to it `x` places to right preserving the sign bit. The `>>>` operator however is the unsigned right shift operator. That means that it’ll shift the bits to the right, filling in the left-hand bits with 0’s.

From my experiments, I’m hitting a couple of issues. The main one is that I think Xojo’s `Bitwise.ShiftRight()` method is equivalent to Java’s `>>` operator although I’m seeing strange results depending on the `numBits` optional parameter that I don’t fully understand. If I’m correct in assuming that `Bitwise.ShiftRight()` is equivalent to `>>`, does anyone have an approach I can use to mimic the `>>>` operator?

sample code ?
there are 2 kinds of shifts and sounds like you need logical shift not arithmetic

OK. Starting from basics.

## `>>` Operator

Here’s some Java code using `>>`:

``````long a1 = -2 >> 1;
long b1 = 0 >> 1;
long c1 = -1 >> 1;
long d1 = 1 >> 1;
long e1 = 100 >> 1;
long f1 =  -2147483648 >> 1; // NB: shifting `int` min
long g1 =  2147483647 >> 1; // NB: shifting `int` max
``````

Here’s the corresponding Xojo code:

``````Var a1 As Int64 = Bitwise.ShiftRight(-2, 1)
Var b1 As Int64 = Bitwise.ShiftRight(0, 1)
Var c1 As Int64 = Bitwise.ShiftRight(-1, 1)
Var d1 As Int64 = Bitwise.ShiftRight(1, 1)
Var e1 As Int64 = Bitwise.ShiftRight(100, 1)
Var f1 As Int64 = Bitwise.ShiftRight(-2147483648, 1) // NB: shifting Int32 min
Var g1 As Int64 = Bitwise.ShiftRight(2147483647, 1) // NB: shifting Int32 max
``````

Here’s the output:

Variable Java Xojo Correct?
a1 -1 9223372036854775807 NO
b1 0 0 YES
c1 -1 9223372036854775807 NO
d1 0 0 YES
e1 50 50 YES
f1 -1073741824 9223372035781033984 NO
g1 1073741823 1073741823 YES

## `>>>` Operator

Since I know I’m on the wrong track, I’ll post some Java code and the expected output.

``````long a2 = -2 >>> 1;
long b2 = 0 >>> 1;
long c2 = -1 >>> 1;
long d2 = 1 >>> 1;
long e2 = 100 >>> 1;
long f2 =  -2147483648 >>> 1; // NB: shifting `int` min
long g2 =  2147483647 >>> 1; // NB: shifting `int` max
``````

Trying a different approach with Xojo, I think `x >> y` equates to `x \ (2^y)` so:

``````Var a2 As Int64 = -2\(2^1)
Var b2 As Int64 = 0\(2^1)
Var c2 As Int64 = -1\(2^1)
Var d2 As Int64 = 1\(2^1)
Var e2 As Int64 = 100\(2^1)
Var f2 As Int64 = -2147483648\(2^1) // NB: shifting Int32 min
Var g2 As Int64 = 2147483647\(2^1) // NB: shifting Int32 max
``````

Here’s the output:

Variable Java Xojo Correct?
a2 2147483647 -1 NO
b2 0 0 YES
c2 2147483647 0 NO
d2 0 0 YES
e2 50 50 YES
f2 1073741824 -2147483648 NO
g2 1073741823 1073741823 YES

Where am I going wrong?

is bitwise shifts
is \2

bitwise operates on 64 bits unless you tell it otherwise

``````Var initial As Int32 = -2
Var a2 As Int32 = bitwise.shiftright(initial,1,32)
initial = 0
Var b2 As Int32 = bitwise.shiftright(initial,1,32)
initial = -1
Var c2 As Int32 = bitwise.shiftright(initial,1,32)
initial = 1
Var d2 As Int32 = bitwise.shiftright(initial,1,32)
initial = 100
Var e2 As Int32 = bitwise.shiftright(initial,1,32)
initial = -2147483648
Var f2 As Int32 = bitwise.shiftright(initial, 1,32) // NB: shifting Int32 min
initial = 2147483647
Var g2 As Int32 = bitwise.shiftright(initial,1,32) // NB: shifting Int32 max

Break
``````

for >> use something like this (I think the value reported for C1 should be 0 in java)

``````// handling >>
initial = -2
Var a1 As Int64 = initial\(2^1)
initial = 0
Var b1 As Int64 = initial\(2^1)
initial = -1
Var c1 As Int64 = initial\(2^1)
initial = 1
Var d1 As Int64 = initial\(2^1)
initial = 100
Var e1 As Int64 = initial\(2^1)
initial = -2147483648
Var f1 As Int64 = initial\(2^1) // NB: shifting Int32 min
initial = 2147483647
Var g1 As Int64 = initial\(2^1) // NB: shifting Int32 max
``````

Not according to NetBeans:

I’ve tried substituting in your suggestions @npalardy but the answers are still incorrect.

You can see why this has been driving me nuts all day…

except for the weird result you get for c1 this matches the java >> code and results you posted earlier

``````Dim initial As Int32
// handling >>
initial = -2
Var a1 As Int32 = initial\(2^1)
If a1 <> -1 Then
Break
End If

initial = 0
Var b1 As Int32 = initial\(2^1)
If b1 <> 0 Then
Break
End If

initial = -1
Var c1 As Int32 = initial\(2^1)
If c1 <> -1 Then
Break
End If

initial = 1
Var d1 As Int32 = initial\(2^1)
If d1 <> 0 Then
Break
End If

initial = 100
Var e1 As Int32 = initial\(2^1)
If e1 <> 50 Then
Break
End If

initial = -2147483648
Var f1 As Int32 = initial\(2^1) // NB: shifting Int32 min
If f1 <> -1073741824 Then
Break
End If

initial = 2147483647
Var g1 As Int32 = initial\(2^1) // NB: shifting Int32 max
If g1 <> 1073741823 Then
Break
End If

initial = -2
Var a2 As Int32 = bitwise.shiftright(initial,1,32)
If a2 <> 2147483647 Then
Break
End If

initial = 0
Var b2 As Int32 = bitwise.shiftright(initial,1,32)
If b2 <> 0 Then
Break
End If

initial = -1
Var c2 As Int32 = bitwise.shiftright(initial,1,32)
If c2 <> 2147483647 Then
Break
End If

initial = 1
Var d2 As Int32 = bitwise.shiftright(initial,1,32)
If d2 <> 0 Then
Break
End If

initial = 100
Var e2 As Int32 = bitwise.shiftright(initial,1,32)
If e2 <> 50 Then
Break
End If

initial = -2147483648
Var f2 As Int32 = bitwise.shiftright(initial, 1,32) // NB: shifting Int32 min
If f2 <> 1073741824 Then
Break
End If

initial = 2147483647
Var g2 As Int32 = bitwise.shiftright(initial,1,32) // NB: shifting Int32 max
If g2 <> 1073741823 Then
Break
End If
``````
``````public class Main {
public static void main(String[] args) {

System.out.println(" >> " ) ;

long a1 = -2 >> 1;
System.out.println(" a1 = " + a1) ;

long b1 = 0 >> 1;
System.out.println(" b1 = " + b1) ;

long c1 = -1 >> 1;
System.out.println(" c1 = " + c1) ;

long d1 = 1 >> 1;
System.out.println(" d1 = " + d1) ;

long e1 = 100 >> 1;
System.out.println(" e1 = " + e1) ;

long f1 =  -2147483648 >> 1; // NB: shifting `int` min
System.out.println(" f1 = " + f1) ;

long g1 =  2147483647 >> 1; // NB: shifting `int` max
System.out.println(" g1 = " + g1) ;

System.out.println(" >>> " ) ;

long a2 = -2 >>> 1;
System.out.println(" a2 = " + a2) ;

long b2 = 0 >>> 1;
System.out.println(" b2 = " + b2) ;

long c2 = -1 >>> 1;
System.out.println(" c2 = " + c2) ;

long d2 = 1 >>> 1;
System.out.println(" d2 = " + d2) ;

long e2 = 100 >>> 1;
System.out.println(" e2 = " + e2) ;

long f2 =  -2147483648 >>> 1; // NB: shifting `int` min
System.out.println(" f2 = " + f2) ;

long g2 =  2147483647 >>> 1; // NB: shifting `int` max
System.out.println(" g2 = " + g2) ;

}
}
``````

huh … dunno how to explain -1 shifted right still being -1 in java

but thats the only difference I can find

heres my code

1 Like

For unknown reasons, shift right of signed numbers in Java does not fill the bit that shifted with 0. I would NEVER expect this.

-1 = 1111 1111
-1 >> 1 = 1111 1111

IMHO, it should be:
-1 >> 1 = 0111 1111

Seems the >>> operator works the way all other languages do for a proper shift right.
No idea why it’s that way in Java. I do not program in java, so maybe there’s a valid reason for this. To me it makes no sense. First time in my life I’ve heard of a “Signed shift”.

https://www.tutorialspoint.com/Bitwise-right-shift-operator-in-Java

In the first post:

What you refer to is >>>:

@npalardy: As usual, your code is solid.

In summary, to shift an `Int32` using `>>` do this:

``````Public Function RShift32(v As Int32, shift As Integer) As Int32
// HACK: I hate this but this is what Java does...
If value = -1 And shift = 1 Then Return -1
Return v \ (2^shift)
End Function
``````

To do an unsigned shift on an `Int32` using `>>>` do this:

``````Public Function RShiftU32(v As Int32, shift As Integer) As Int32
Return Bitwise.ShiftRight(value, shift, 32)
End Function
``````

The answers are the same is you cast the resulting `Int32` into an `Int64`.

If anyone can think of a more elegant solution than my hack to check for shifting `-1` one position then do speak up. It’s ugly as sin and reduces performance by do a conditional check every invocation.

I need to do some more testing now to replicate the `>>` and `>>>` operators when shifting Java `long` types (which are `Int64`). My initial runs through my test suite are now all broken because this obviously is causing issues with `Int64`

Yep. One of the many peculiarities in Java.

Welcome to the forum btw.

1 Like

This is why I was saying there are 2 kinds of shifts

1. arithmetic shift - which will retain signs
2. logical shift - which will zero fill and does NOT consider the item “signed”

there are additional operations (roll which is like a special form of shifting) but there are no Xojo language constructs which expose rolls

Do you have a computer science background @npalardy? You do seem to know your stuff around this.

@npalardy I think I might have cracked it!!!

Full disclosure: I posted this on the main Xojo forum too - I had got some help from people there also (not to mention @npalardy posting in both places - superstar!).

The issue is that Java assumes that all numeric literals are `Int32` unless specifically stipulated by suffixing the literal with `L` . since Xojo infers that numeric literals are `Int64` by default, we begin to see the issue.

The solution is that we 3 need methods. One to replicate Java’s `>>` signed right shift operator:

``````Function RightShift(v As Int64, s As Integer) as Int64
If v >= 0 Then
Return Bitwise.ShiftRight(v, s)
Else
If s = 1 Then
Return Bitwise.BitOr(&h8000000000000000, Bitwise.ShiftRight(v, s))
End
Return Bitwise.BitOr(Bitwise.ShiftLeft(-1, 64 - s), Bitwise.ShiftRight(v, s))
End
End Function
``````

And we need two methods to handle Java’s `>>>` unsigned right shift operator because how Java handles them depends on whether the left hand operand is an `int` ( `Int32` ) or a `long` ( `Int64` ).

To pass an `Int32` :

``````Function RightShiftU32(v As Int32, s As Integer) As Int32
Return Bitwise.ShiftRight(v, s, 32)
End Function
``````

To pass an `Int64` :

``````Function RightShiftU64(value As Int64, shift As Integer) As Int64
Return Bitwise.ShiftRight(value, shift, 64)
End Function
``````

`Int4 >> x` Proof:

``````///
' Tests long = int >> x
///

// Values that fit into an Int32.
Var a As Int64 = MathsKit.RightShift(-2, 1)
Var b As Int64 = MathsKit.RightShift(0, 1)
Var c As Int64 = MathsKit.RightShift(-1, 1)
Var d As Int64 = MathsKit.RightShift(1, 1)
Var e As Int64 = MathsKit.RightShift(100, 1)
Var f As Int64 = MathsKit.RightShift(-2147483648, 1)
Var g As Int64 = MathsKit.RightShift(2147483647, 1)
Var h As Int64 = MathsKit.RightShift(2147483647, 5)
Var i As Int64 = MathsKit.RightShift(-1, 30)

Assert.AreEqual(-1, a)
Assert.AreEqual(0, b)
Assert.AreEqual(-1, c)
Assert.AreEqual(0, d)
Assert.AreEqual(50, e)
Assert.AreEqual(-1073741824, f)
Assert.AreEqual(1073741823, g)
Assert.AreEqual(67108863, h)
Assert.AreEqual(-1, i)

// Use values that would only fit in an Int64.
Var j As Int64 = MathsKit.RightShift(2147483999, 1)
Var k As Int64 = MathsKit.RightShift(-2147483999, 30)

Assert.AreEqual(1073741999, j)
Assert.AreEqual(-3, k)
``````

`Int32 >>> x` Proof

``````///
' Tests long = int >>> x
///

Var a As Int64 = MathsKit.RightShiftU32(-2, 1) ' -2 >>> 1
Var b As Int64 = MathsKit.RightShiftU32(0, 1) ' 0 >>> 1
Var c As Int64 = MathsKit.RightShiftU32(-1, 1) ' -1 >>> 1
Var d As Int64 = MathsKit.RightShiftU32(1, 1) ' 1 >>> 1
Var e As Int64 = MathsKit.RightShiftU32(100, 1) ' 100 >>> 1
Var f As Int64 = MathsKit.RightShiftU32(-2147483648, 1) ' -2147483648, >>> 1
Var g As Int64 = MathsKit.RightShiftU32(2147483647, 1) ' 2147483647 >>> 1

Assert.AreEqual(2147483647, a)
Assert.AreEqual(0, b)
Assert.AreEqual(2147483647, c)
Assert.AreEqual(0, d)
Assert.AreEqual(50, e)
Assert.AreEqual(1073741824, f)
Assert.AreEqual(1073741823, g)

``````

`Int64 >>> x` Proof:

``````///
' Tests long = long >>> x
///

Var a As Int64 = MathsKit.RightShiftU64(-2, 1) ' -2 >>> 1
Var b As Int64 = MathsKit.RightShiftU64(0, 1) ' 0 >>> 1
Var c As Int64 = MathsKit.RightShiftU64(-1, 1) ' -1 >>> 1
Var d As Int64 = MathsKit.RightShiftU64(1, 1) ' 1 >>> 1
Var e As Int64 = MathsKit.RightShiftU64(100, 1) ' 100 >>> 1
Var f As Int64 = MathsKit.RightShiftU64(-2147483648, 1) ' -2147483648, >>> 1
Var g As Int64 = MathsKit.RightShiftU64(2147483647, 1) ' 2147483647 >>> 1
Var h As Int64 = MathsKit.RightShiftU64(2147483999, 1) ' 2147483999 >>> 1

Assert.AreEqual(9223372036854775807, a)
Assert.AreEqual(0, b)
Assert.AreEqual(9223372036854775807, c)
Assert.AreEqual(0, d)
Assert.AreEqual(50, e)
Assert.AreEqual(9223372035781033984, f)
Assert.AreEqual(1073741823, g)
Assert.AreEqual(1073741999, h)
``````

This is when Norman finds a bug and posts a more elegant solution in like 2 minutes time!

I do have a CS degree

dang I could swear I posted something about using CType to make sure a literal gets treated as whatever specific size you wanted

I think you did actually:

``````
Public Function RShift(v As Uint8, shift As Integer) As Uint8
Return Bitwise.ShiftRight(v, shift)
End Function

Public Function RShift(v As Uint16, shift As Integer) As Uint16
Return Bitwise.ShiftRight(v, shift)
End Function

Public Function RShift(v As Uint32, shift As Integer) As Uint32
Return Bitwise.ShiftRight(v, shift)
End Function
``````

You’ve been super helpful mate. Thanks.

interesting … java actually seems to mask off the shift parameter so you cannot shift more bits than exist
as if these were

``````Public Function RShift(v As Uint8, shift As Integer) As Uint8
Return Bitwise.ShiftRight(v, shift and 7)
End Function

Public Function RShift(v As Uint16, shift As Integer) As Uint16
Return Bitwise.ShiftRight(v, shift and 15)
End Function

Public Function RShift(v As Uint32, shift As Integer) As Uint32
Return Bitwise.ShiftRight(v, shift and 31)
End Function
``````

which has the effect of treating a shift of 32 bits right on a 32 bit value as if it was NOT shifted at all (same for shifting and 8 bit value right 8 times, etc)
this explains some of the behaviour we’ve seen

EDIT : except when it doesnt - I hate docs that are wrong

Which docs - Java or Xojo?

Java
The xojo docs are just incomplete in many areas

1 Like