Reverse bits in a byte (opposite order)

[Myicq]

This is probably totally obvious.. but my skills in bit operations could be improved a lot.

I have a string of bytes where I would like to reverse the order of the bits.

Principle:

; Input = 01000000  = 0x40
; Output = 00000010 = 0x02


consolewrite(reversebits(0x40))    ; returns 0x02
consolewrite(reversebits(0x20))    ; returns 0x04


func reversebits($inp)
   ; ...
   ; $out = ...__...
   return $out
endfunc

Can it be done with simple bitrotate ?

[junkew]

a lookuptable is probably fastest

http://graphics.stanford.edu/~seander/bithacks.html

[funkey]

[Myicq]

a lookuptable is probably fastest

http://graphics.stanford.edu/~seander/bithacks.html

Thanks for the link.

My skills in reading C code could be better.. are you thinking like "create an array with pre-calculated values and return $bitarray[input]" ? I guess there will be a maximum of 254 different values (0x00 and 0xFF should be obvious), so this is doable without too much trouble.

If I understood this idea wrong, let me know.

Edit: I would also think associative array  (Windows Object) or a simple sqLite in-Memory database would be possible. Question is which of the 3 would be the fastest ?

Edited February 12, 2014 by Myicq

[UEZ]

Try this:

ConsoleWrite(Hex(ReverseBits(0x40), 8) & @LF)
ConsoleWrite(Hex(ReverseBits(0x20), 8) & @LF)

Func ReverseBits($n) ;coded by UEZ 2014
    Local $iBits
    Switch Ceiling(Log($n + 1) / Log(2))
        Case 0 To 8
            $iBits = 8
        Case 9 To 16
            $iBits = 16
        Case 17 To 32
            $iBits = 32
        Case Else
            $iBits = 64
    EndSwitch
    Local $iCount = 0, $i, $j = 0
    For $i = $iBits - 1 To 1 Step - 2
        $iCount += BitAND(BitShift($n, $i), 2 ^ $j)
        $j +=1
    Next
    For $i = 1 To $iBits - 1 Step 2
        $iCount += BitAND(BitShift($n, -$i), 2 ^ $j)
        $j +=1
    Next
    Return $iCount
EndFunc

Edit: code works only for unsigned integer numbers!

Br,

UEZ

Edited February 13, 2014 by UEZ

[czardas]

The less sophisticated approach, operating on a single byte:

Func _ByteReverse($dByte)
    Local $iRet = 0
    For $i = 0 To 7
        $iRet += 2^(7 -$i)*(BitAND($dByte, 2^$i) = True)
    Next
    Return $iRet
EndFunc

Local $dTest = 0xA0
MsgBox(0, "_ByteReverse(" & $dTest & ")", _ByteReverse($dTest))

Edited February 12, 2014 by czardas

[Myicq]

Well, thank you very much to all contributors to this, especially you UEZ. I am astounded you have time to have a life outside helping people out here. Thumbs up!!

Did a small comparisons with different methods I had in mind.

Results, made on my not-extremely-fast Intel i3 machine, for 100.000 iterations:

• In-Memory SQLite database using _SQLite_QuerySingleRow on integer fields : 45-50 seconds (this really surprised me...)
• UEZ function as above: 3.9 seconds
• Associative Array, using UDF from Ward (AssociativeArray.au3): 2.4 seconds
• Normal linear array (256 positions) : 0.2 seconds

Although normal array is by far the fastest, I can recommend UEZ version for anything about 8 bits. Having 2^32 lines defining array values is not practical at all.

I have found a guy who did an informative Excel sheet on the topic. Adding to this, I have put the AutoIT codes to fill array values. Sheet is attached.

So once again thanks to UEZ. Great work! And to junkew for suggestion on fastest way.

reverse_bits.xls

[czardas]

You will always get faster results with a lookup table. I also ran some tests of my own and the results were quite positive.

[czardas]

@UEZ - Your code doesn't seem to take into account the sign bit for 32bit (or 64bit) integers - nor would my method without modification.

Edited February 13, 2014 by czardas

[UEZ]

Yes, you are right czardas. I forgot to mention it.

 

Br,

UEZ

Edited February 13, 2014 by UEZ

[Gianni]

... another way

shorter but a few bits slower

ConsoleWrite(Hex(ReverseBits(0x40), 8) & @LF)
ConsoleWrite(Hex(ReverseBits(0x20), 8) & @LF)

Func ReverseBits($Byte)
    Local $out = 0
    For $i = 0 To 7
        $out = BitShift($out, -1)
        $out = BitOR($out, BitAND($Byte, 2 ^ $i) > 0)
    Next
    Return $out
EndFunc   ;==>ReverseBits

EDIT:

or only by manipulation of the bits

ConsoleWrite(Hex(ReverseBits(0x40), 8) & @LF)
ConsoleWrite(Hex(ReverseBits(0x20), 8) & @LF)

Func ReverseBits($Byte)
    Local $out = 0
    For $i = 0 To 7
        $out = BitOR(BitShift($out, -1), BitAND($Byte, 1))
        $Byte = BitShift($Byte, 1)
    Next
    Return $out
EndFunc   ;==>ReverseBits

Edited February 13, 2014 by PincoPanco

[UEZ]

I modified my example to accept also negative numbers.

 

ConsoleWrite(Hex(ReverseBits(0x20)) & @LF)
ConsoleWrite(Hex(ReverseBits(12345678)) & @LF)
ConsoleWrite(Hex(ReverseBits(-8)) & @LF)
ConsoleWrite(Hex(ReverseBits(-12345678)) & @LF)

Func ReverseBits($n) ;coded by UEZ 2014 : from 11010010 (210) -> 01001011 (75)
    Local $iBits, $iLength = Ceiling(Log(Abs($n) + 1) / Log(2)), $m = $n
    $iBits = Ceiling($iLength / 4) * 4
    If $n < 0 Then $n = 2^$iBits - Abs($n)
    Local $iNumber = 0, $i, $j = 0
    For $i = $iBits - 1 To 1 Step - 2
        $iNumber += BitAND(BitShift($n, $i), 2 ^ $j)
        $j += 1
    Next
    For $i = 1 To $iBits - 1 Step 2
        $iNumber += BitAND(BitShift($n, -$i), 2 ^ $j)
        $j += 1
    Next
    If $m < 0 Then
        Local $iHex = Hex($iNumber, $iBits / 4), $i64 = "FFFFFFFFFFFFFFFFF"
        Return Dec($iHex & StringMid($i64, 1, 16 - StringLen($iHex)))
    EndIf
    Return $iNumber
EndFunc

It seems to work.

 

Br,

UEZ

Edit1: made the function shorter

Edited February 14, 2014 by UEZ