bit rotation

[nkad]

Can someone give me some pointers on bit rotation. how do I rotate to the left or right a given number of bits.

Thanks!

[krtxmrtz]

Left rotation is equivalent to shifting all bits one (or more) place(s) to the left, i.e. multiplying by 2 as many times as the required number of places. The leftmost bit, which can't go any farther to the left is "rotated" to become the rightmost one. For example, if you're working with 8-bit bytes:

00101101 becomes 01011010
10111000 becomes 01110001

The right rotation is the same story but now you shift to the right (perform integer division by 2). Likewise, the rightmost bit becomes the leftmost one. For instance:

01100011 becomes 10110001
10101100 becomes 01010110

In assembly language you can make these rotations by means of handy instructions available. In vb (as far as I know) there aren't any such instructions and you'd have to check the leftmost (or rightmost) bit before doing the product (or division) by 2 and calculate according to the result of this test.

[jim mcnamara]

You didn't specify a language:

C:

long  s=27;
s<<2;  // shift left 2 bits;
s>>4; // shift left 4 bits

or in VB:

Const LEFT = 1
Const RIGHT =2
Function shiftRight(i as long,bits as Integer,RightorLeft as Integer) as long
       dim x as integer
if RightorLeft=RIGHT then
       for x = 1 to bits 
            i = i \ 2
       next
       shiftRight=i
End if
if RightorLeft = LEFT then
       for x = 1 to bits 
            i = i * 2
       next
       shiftRight=i
End if
end Function

[MR2]

Jim, both those solutions are for shift's, not rotates.

To rotate purely in VB, you need to test and save either the MSBit or the LSBit depedning on direction, and then set the opposite bit after a shift. e.g.

Public Function RotateRight(ByVal NewRot As Byte) As Byte

Dim blnBit As Boolean

' save LS bit
blnBit = ((NewRot And &H1) = &H1)

' shift right by integer division
NewRot = NewRot \ 2

' restore the saved bit in the MS bit
If blnBit Then NewRot = NewRot Or &H80

' return the result
RotateRight = NewRot

End Function

A tiny bit more tricky for a rotate left as we have to take into account a possible overflow.

Public Function RotateLeft(ByVal NewRot As Byte) As Byte

Dim blnBit As Boolean

' save MS bit
blnBit = ((NewRot And &H80) = &H80)

' ensure MS bit is clear to prevent overflow
NewRot = NewRot And Not &H80

' shift left by multiplying by 2
NewRot = NewRot * 2

' restore the saved bit in the LS bit
If blnBit Then NewRot = NewRot Or &H1

' return the result
RotateLeft = NewRot

End Function

You should be able to convert this to use whatever integer types you want. You could also modify them to specify number of bits to rotate.