Rotating bits in N-bit words

[davido]

In the following thread some neat ASM code was presented to rotate bits in 12- and 24-bit words.
http://www.purebasic.fr/english/viewtop ... 76#p432676

I present here some code in a Module to rotate bits in words of any number of bits up to the native integer maximum. It only uses PB code; no ASM.

It also appears to be a little faster.

Lets hope some one takes up the challenge to make it faster yet!

Code: Select all

DeclareModule Rot
  Macro RoR(Num,Bits,Size)
    Ans = ((%1 << Bits -1) & Num) << (Size - Bits) + Num >> Bits
  EndMacro
  
  Macro Rol(Num,Bits,Size)
    Ans = Num >> (Size - Bits) + ((%1 << (Size - Bits) - 1) & Num) << Bits  
  EndMacro
EndDeclareModule

Module Rot
  EnableExplicit
  Global Num.i, Bits.i, Size.i
EndModule




EnableExplicit
Global M.i,R.i, A$, B$, Ans.i, Dt.i, BitsToRotate.b



BitsToRotate = 17
B$ = ""
For M = 0 To BitsToRotate - 1
  Rot::RoL($1e0d6,M,BitsToRotate)
  B$ + RSet(Str(M),2,"0") + ": " + RSet(Bin(Ans),BitsToRotate,"0") + "   (" + Str(Ans) + ")" + Chr(10)
Next M




R = 3

Dt = ElapsedMilliseconds()

For M = 1 To 10000000
  Rot::RoL($1e0d6,R,BitsToRotate)
Next M

MessageRequester("10,000,000 iterations, in: "+ Str(ElapsedMilliseconds() - dt) + " ms",B$)

[wilbert]

The code Psychophanta posted in the other thread, uses a modulo.
In case of your example, if you rotate a 17 bit value 36 bits to the left, that should be equal to a rotate of 2 bits to the left (17 + 17 + 2).

[davido]

@wilbert,

I did think that that might be a problem, however, I assumed that rotations greater than N would be unreasonable.

I bow to your greater knowledge.

Thank you.

[wilbert]

I did think that that might be a problem, however, I assumed that rotations greater than N would be unreasonable.

Most of the time you won't have rotations that are greater. I was mainly pointing this out because the asm commands rol and ror work this way and as an explanation why your PB source could be faster compared to the ASM source. Division / modulo is just a very time consuming operation.