Bit Shifting Right Help

I have wasted most of the day on this problem :frowning:

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 bananas 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?

ah the joy of having 2 different kinds of shifts

  1. arithmetic
  2. logical

bitwise.shiftright is a LOGICAL shift right and will not necessarily preserve the sign bit
but you DO need to use the numbits parameter

\ 2 is a arithmetic shift and will

edit : sample code ???

see my reply on “that other forum” :stuck_out_tongue:

aren’t we talking about the difference between SHR and ROR operations…
where ROR rotates the least significant bit to the most significant position. where SHR just drops it
and SHL and ROL do the opposite

more or less
intel calls them SAR (shift arithmetic right) and SHR (shift right) and they behave different as far as the sign bit is concerned

rotate tends to have slightly different semantics and may roll the lowest bit into the sign (or vice verse when rotating left or right)
as you noted

:slight_smile: my references to SHR, ROR, SHL and ROL come from WAY back, as in when I was writing Assembler for Z80 processors

Based on your description, the Xojo functions would be equivalent to <<< and >>>. To fake << and >>:

Preserve the sign. Shift left one bit, then right x+1. Restore the sign.

Preserve the sign. Shift left x. Restore the sign.

no need to fake anything

and <<< are bitwise functions

and << are power of 2 division or multiplication

I already gave Garry the code on “that other forum that cannot be named”

Intel just has sooo many more instructions for just about everything imaginable

but the big difference is the kind of shift (I would guess Z80 had something similar)

if you have an 8 bit signed value like &b10000001 and do an arithmetic shift right once you want the sign to stay the same
you should get &b10000000

with a logical shift you shift all the bits as you arent treating the value as a “signed value”
its just a pile of bits
in that case you would get &b01000000

vastly different results especially IF you believe in both cases you have a “signed uint8” :stuck_out_tongue:

Despite some suggestions, I’m still struggling. Here’s some code to illustrate:

>> 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?

[quote=473401:@Garry Pettet]
Where am I going wrong?[/quote]
you have the wrong shifts in use to match Xojo and Java
javas >> should be turned into Xojo code using powers of 2 ie/ var \ (2^# bits to shift)
javas >>> should be turned into ode using bitwise shifts ie/ bitwise.shiftright(var, num bits, size of var holding value to shift)

posted more code and a full sample on that other forum

Signed shift right in 64 bit:

[code]Public Function SShiftRight(v As Int64, numShift As Integer = 1) as Int64
If v>=0 Then
Return Bitwise.ShiftRight( v, numShift )
Else
If numShift=1 Then
Return Bitwise.BitOr( &h8000000000000000, Bitwise.ShiftRight( v, numShift ) )
End
Return Bitwise.BitOr( Bitwise.ShiftLeft( -1, 64 - numShift ), Bitwise.ShiftRight( v, numShift ) )
End
End Function

// Test
Dim i As int64
i = SShiftRight(-2)
break // check i in the debugger
i = SShiftRight(0)
i = SShiftRight(-1)
i = SShiftRight(1)
i = SShiftRight(100)
i = SShiftRight(-2147483648)
i = SShiftRight(2147483647)

[/code]

Ok so,

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.

The only exception to this rule is the hack in the first code block. In Java, -1 >> 1 == -1 but the Xojo code returns 0. 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).

Handling 32 bit ints is much simpler than 64 bit in Xojo. The same logical operators can handle them “bitwisely”, but 64 bit needs the Bitwise module.

My answer is for 64 bit, based on your demo and samples.

Your answer can handle values in the range ?2147483648 to +2147483647.
Mine is extended to -9,223,372,036,854,775,808 to +9,223,372,036,854,775,807.

The “Ifs” I did are for speed things a bit up, as the mutibit shift of a negative number have a higher cost.

The math oneliner for this costs more than your “If”.

Ok, your later 32 bit math has quirks too. The correct answer to -1073741824 sshr 30 is -1. And sshr 31 also is -1. But you get 0 too due to the same effect that imposed you to create that prior If.

Any idea why this is the case?

I shall try implementing your solution when I get back to my office later.

Integer division is not the same as a signed shift right. -1 / 2 = -0.5 and truncated you get a 0. And that’s the root of ALL your problems, there are several combinations of values and shift values that gets you a 0 instead of a -1 due to this.

[quote=473421:@Rick Araujo]Public Function SShiftRight(v As Int64, numShift As Integer = 1) as Int64
If v>=0 Then
Return Bitwise.ShiftRight( v, numShift )
Else
If numShift=1 Then
Return Bitwise.BitOr( &h8000000000000000, Bitwise.ShiftRight( v, numShift ) )
End
Return Bitwise.BitOr( Bitwise.ShiftLeft( -1, 64 - numShift ), Bitwise.ShiftRight( v, numShift ) )
End
End Function[/quote]
You are a genius Rick!! It works seemingly perfectly for >>. Thank you so much.

Since you seem well informed, I am assuming my method for an unsigned shift:

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

Is good for both Int64 and Int32 data types?

the only case where the code I gave you did not match was -1

-65536 sshr 25 is -1, Garry’s old code gets 0.

-65536 = &hFFFF0000