Shift Numbits explanation please

Eric_Wilson · April 26, 2019, 6:39pm

I am trying to get my head around the Numbits parameter of ShiftRight and ShiftLeft.

The following code results in &b101

dim intTest as uint8 = &b111 intTest = ShiftRight(intTest,1,2) strResult as String = Bin(intTest)

However intTest = ShiftRight(intTest,2,2) results in &b0

While intTest = ShiftLeft(intTest,1,2) results in &b110

While intTest = ShiftRight(intTest,2,2) results in &b0

The ShiftRight and ShiftLeft documentation doesn’t explain how this works - looks like some kind of masking numbered from right to left?
Can anyone fill me in please? Also, what is the CPU cost: is Numbits an extra operation or part of Shifting?
Some understanding around this would be much appreciated…

Eric_Wilson · April 26, 2019, 7:35pm

That last example should be:

While intTest = ShiftLeft(intTest,2,2) also results in &b0

I’m stumped as to what Numbits does.

Norman_Palardy · April 26, 2019, 8:04pm

numbits is how many bits to use
as if you had first masked with &b1 with numbits bits set (ie/ numbits = 2 is &b11 etc)

dim intTest as uint8 = &b111
// intTest = ShiftRight(intTest,1,2)
// is roughly
intest = intest and &b11
intTest = ShiftRight(intTest,1)

and so if you set numbits = 2 and shift 2 you get

dim intTest as uint8 = &b111
// intTest = ShiftRight(intTest,1,2)
// is roughly
intest = intest and &b11 // which leaves intest = &b11
intTest = ShiftRight(intTest,2)

which makes intTest = 0

Eric_Wilson · April 26, 2019, 8:23pm

Thanks for your reply Norman. Why then does intTest = ShiftRight(intTest,2,2) not result in &b1 ?
If the reason is because the highest order bit of 111 is outside the mask of 2 digits, why then does intTest = ShiftLeft(intTest,1,2) results in &b110 ? since the resulting highest order bit is outside the numbit mask? If it is because the numbit mask floats, why then does intTest = ShiftLeft(intTest,2,2) not result in &b1100 ?

Norman_Palardy · April 26, 2019, 8:43pm

ah more like it also ORS things together at the end
the shift on affects however many bits you specify

so

 dim test as integer = &b11110110
 dim inttest as integer = shiftright(test, 1, 2)
 // intest is now &b11110101

shifts the low 2 bits (numbits) 1 position right
so inttest ends up as &b11110101

so if you had to code this by hand

dim intTest as uint8 = &b111
// intTest = ShiftRight(intTest,1,2)
// is roughly
dim tmp as integer =  intTest and &b11 
intTest = intTest XOR tmp 
tmp = ShiftRight(tmp,2)
intTest = intTest OR tmp

Eric_Wilson · April 27, 2019, 1:42pm

The way I understand it, the effect of uintTest = uintTest XOR tmp would be to flip every 1 in the numbit range of uintTest to a 0 before the shift. So at this point the value of uintTest would become &b100
The effect of tmp = ShiftRight(tmp,2) would change tmp to become &b00
Thus the effect of uintTest = uintTest Or Tmp would make the value of uintTest become &b100 but in real life the result is actually &b110
Or maybe I missed a step?

Norman_Palardy · April 27, 2019, 2:00pm

or maybe I wrote it wrong since I just wrote it in the forum

yeah thats more likely since the upper using shift with numbits shifts 1 spot
the lower using the hand written xor shift and or shifts 2

these two are more similar

Dim intTest As UInt8 = &b11110110
Dim tmp As Integer =  intTest And &b11 // <<<<< numbits
intTest = intTest Xor tmp // clear the lower numbits from inttest
tmp = ShiftRight(tmp,1) // shift numbits bits right 1 spot
intTest = intTest Or tmp // and put the resulting numbits shifted back in
// intest is now &b11110101

Break

Dim test1 As Integer = &b11110110
Dim inttest1 As Integer = shiftright(test1, 1, 2) // shift the lower 2 bits (numbits) right 1 position
// intest1 is now &b11110101

Break

Eric_Wilson · April 27, 2019, 2:08pm

After a few more experiments it seems Numbits shifts the specified number lower order of bits, overwriting bits when shifting to the left and replacing former bits with zeros when shifting to the right. Except when numbits = the amount of shift all bits are set to zero. Seems like a bug to me.

Norman_Palardy · April 27, 2019, 2:14pm

not at all
basically if you shift &b11 right 2 what you’ve actually shifted right is &b00000011 so right 2 would roll in more 0’s
and f you shift &b11 left 2 you get &b1100

shift always shift in 0’s

Norman_Palardy · April 27, 2019, 2:39pm

and I see my manual code is still wrong
numbits is both the number of bits to mask OUT and the number of bits to replace in the original value
which is why the shiftleft behaves as it does

numbits is always the number of lower order bits to deal with

Public Function manualShiftLeftNumbits(value as Uint8, shifts as integer, numbits as integer) as uint8
  Dim tmpmask As UInt8
  
  For i As Integer = 1 To numbits
    If i = 1 Then
      tmpmask = &b1
    Else
      tmpmask = shiftleft(tmpmask ,1) Or &b1
    End If
  Next
  
  // manually doing the shift right of numbits
  Dim intTest As UInt8 = value
  
  Dim tmp As Integer =  intTest And tmpmask 
  intTest = intTest Xor tmp 
  tmp = ShiftLeft(tmp,shifts)
  intTest = intTest Or (tmp And tmpmask)
  
  Return inttest
  
End Function

Public Function manualShiftRightNumbits(value as Uint8, shifts as integer, numbits as integer) as uint8
  Dim tmpmask As UInt8
  
  For i As Integer = 1 To numbits
    If i = 1 Then
      tmpmask = &b1
    Else
      tmpmask = shiftleft(tmpmask ,1) Or &b1
    End If
  Next
  
  // manually doing the shift Left of numbits
  Dim intTest As UInt8 = value
  
  Dim tmp As Integer =  intTest And tmpmask 
  intTest = intTest Xor tmp 
  tmp = ShiftRight(tmp,shifts)
  intTest = intTest Or (tmp And tmpmask)
  
  Return inttest
End Function

and the test driver

Dim testvalue As UInt8
Dim shifts As Integer = 1
Dim numbits As Integer = 2


For testvalue = &b00000000 To &b11111111
  Dim manualshiftrightresult As UInt8 = manualShiftRightNumbits(testvalue, shifts, numbits)
  Dim shiftrightresult As Integer = shiftright(testvalue, shifts, numbits)
  
  If manualshiftrightresult <> shiftrightresult Then
    Break
  End If
  
  Dim manualshiftleftresult As UInt8 = manualShiftLeftNumbits(testvalue, shifts, numbits)
  Dim shiftleftresult As Integer = shiftleft(testvalue, shifts, numbits)
  
  If manualshiftleftresult <> shiftleftresult Then
    Break
  End If
  
  If testvalue = &b11111111 Then
    Exit
  End If
Next

Break

FWIW this NEVER hits any break statement here

Eric_Wilson · April 27, 2019, 3:48pm

Thanks Norman, taking what you said into account, here’s where I’m at:

[code]dim intTest as uint32 = &b1111 '4 x 1 bits

intTest = ShiftLeft(intTest, 3, 2) 'Returns &b0
intTest = ShiftLeft(intTest, 3, 3) 'Returns &b0
intTest = ShiftLeft(intTest, 3, 4) 'Returns &b1000
intTest = ShiftLeft(intTest, 3, 5) 'Returns &b11000
intTest = ShiftLeft(intTest, 3, 6) 'Returns &b111000
intTest = ShiftLeft(intTest, 3, 7) 'Returns &b1111000
intTest = ShiftLeft(intTest, 3, 8) 'Returns &b1111000 - the same as 7 numbits[/code]

So it seems when shifting left using Numbits:
(a) Numbits must > Shift and
(b) all high order bits beyond numbits are set to 0 and
© vacated lower order bits are set to 0.

OK, if that’s the deal, that’s the deal… BUT when shifting right:

[code]dim intTest as uint32 = &b11111 '5 x 1 bits

intTest = ShiftRight(intTest, 3, 2) 'Returns &b0
intTest = ShiftRight(intTest, 3, 3) 'Returns &b0
intTest = ShiftRight(intTest, 3, 4) 'Returns &b10001
intTest = ShiftRight(intTest, 3, 5) 'Returns &b11
intTest = ShiftRight(intTest, 3, 6) 'Returns &b11 - the same as 5 numbits[/code]

This is a deal breaker, because there’s no rhyme or reason for the results in relation to the original serial order of intTest bits.
I suspect the bug therefore, as your code seems to prove, is that Xojo has implemented the LeftShift Numbits algorithm for RightShift Numbits too (save for the shifting itself) accounting for unexpected results…

If so, having correctly deduced the relationship between Anding, Xoring, and Oring (which I could not see) for LeftShift , have you any clue as to what the RightShift Numbits algorithm might look like to produce expected results?

As for me, looks like I will have to continue down my present path of knocking unwanted bits off by shifting left then right again (or right and left again). I guess Shifts should be cheaper anyway as no need to load another value from memory or to compare it - although with out-of-order / speculative execution only God knows what’s really happening under the hood.

Norman_Palardy · April 27, 2019, 4:01pm

since I cant look at the implementation and the docs are woefully silent on much about this I’d resort to masking and bit twiddling manually

I posted manual Left and Right shift above

EDIT : based on the sparse comments on http://documentation.xojo.com/api/language/bitwise.html for shift right and left I believe my manual methods above implement this as expected

for instance

Dim intTest As UInt64 = &b1111   '4 x 1 bits
Dim inttest1 As UInt64
Dim manInttest1 As UInt64

intTest1 = ShiftLeft(intTest, 3, 2)  // Returns &b0 
manIntTest1 = manualShiftLeftNumbits(intTest, 3, 2) // returns &b1100 (or 12) by shifting the low 2 bits 3 positions left

Norman_Palardy · April 27, 2019, 4:14pm

and now that I’m looking at this I think youre right that there’s some kind of bug when you do use numbits

Eric_Wilson · April 27, 2019, 4:17pm

Agreed. Appreciate your efforts!

Norman_Palardy · April 27, 2019, 4:26pm

either way the docs are not clear on exactly how things works

I wonder if the shift using numbits only extracts that many bit - shifts and returns a value that is based on those numbits only

ie/ I wonder if its more like

Public Function manualShiftRightNumbits(value as Uint8, shifts as integer, numbits as integer) as uint8
  Dim tmpmask As UInt8
  
  For i As Integer = 1 To numbits
    If i = 1 Then
      tmpmask = &b1
    Else
      tmpmask = shiftleft(tmpmask ,1) Or &b1
    End If
  Next
  
  // manually doing the shift Left of numbits
  Dim intTest As UInt8 = value
  
  Dim tmp As Integer =  intTest And tmpmask 
  intTest = intTest Xor tmp 
  tmp = ShiftRight(tmp,shifts)
  return ( tmp And tmpmask )
  
End Function

interestingly if I apply this change to my manual versions the left shift examples “work” the same as the built in ones but the shift rights dont - they behave like they the previous versions of my manual ones where the original value is ored together with the shifted bits

something is weird

I’d file a but report about this

oh - and use my code or write a version of this that behaves how you expect

Norman_Palardy · April 27, 2019, 4:47pm

<https://xojo.com/issue/55562>

Eric_Wilson · April 28, 2019, 10:26am

Good stuff. I found shifting left then shifting right does get rid of unwanted bits but has to be done as separate statements. With this other bug Xojo seems to over-optimise shifts so that:

ShiftRight(ShiftLeft(uintTest, 2),1) is optimised to be as ShiftLeft(uintTest,1) which is incorrect since the second high bit misses out on being zeroed out as was intended. Thus one must code instead:

uintTest = ShiftLeft(UintTest, 2) uintTest = ShiftRight(UintTest, 1)

Also, not a bug but something to be aware of anyway, is Xojo’s memory blocks are little endian whereas uints are big endian. This means Uint8 <> Byte.

Eric_Wilson · April 28, 2019, 10:45am

Perhaps the Shift optimisation bug helped cause the Numbits bug(s) also.

Norman_Palardy · April 28, 2019, 5:53pm

Lord knows
Any time i’ve had to do bit twiddling like this I always just used and or xor and shift without numbits
And if you’re worried about shift you can use \ 2 to shift right which should turn into a shift right
I’ve not looked at the generated machine code for * 2 to see if that generates a shift left when used with integer types

if so then you could avoid shift left & shift right IF thats of concern based on the results in this thread