Need Help Shifting Bits

Garry · 30 January 2020 19:39

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?

npalardy · 30 January 2020 19:48

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

Garry · 30 January 2020 20:18

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?

npalardy · 30 January 2020 20:49

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

npalardy · 30 January 2020 20:56

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

Garry · 30 January 2020 21:41

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…

npalardy · 30 January 2020 22:06

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

Meestor_X · 31 January 2020 06:45

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

MarkusWinter · 31 January 2020 06:53

@Meestor_X:

In the first post:

What you refer to is >>>:

Garry · 31 January 2020 07:19

@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…

Garry · 31 January 2020 12:15

Yep. One of the many peculiarities in Java.

Welcome to the forum btw.

npalardy · 31 January 2020 16:17

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

arithmetic shift - which will retain signs
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

Garry · 31 January 2020 18:50

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

Garry · 31 January 2020 22:31

@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!

npalardy · 31 January 2020 22:40

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

Garry · 31 January 2020 22:50

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.

npalardy · 1 February 2020 00:29

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

Garry · 1 February 2020 10:52

Which docs - Java or Xojo?

npalardy · 2 February 2020 04:43

Java
The xojo docs are just incomplete in many areas

Need Help Shifting Bits

>> Operator

>>> Operator

`>>` Operator

`>>>` Operator