Reverse bits in a byte (opposite order)

Go to solution Solved by UEZ,

Recommended Posts

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 ?

I am just a hobby programmer, and nothing great to publish right now.

Share on other sites

Programming today is a race between software engineers striving to
build bigger and better idiot-proof programs, and the Universe
trying to produce bigger and better idiots.
So far, the Universe is winning.

Share on other sites

a lookuptable is probably fastest

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

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 by Myicq

I am just a hobby programmer, and nothing great to publish right now.

Share on other sites

• Solution

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 by UEZ

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Share on other sites

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 by czardas
Share on other sites

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

I am just a hobby programmer, and nothing great to publish right now.

Share on other sites

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

Share on other sites

@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 by czardas
Share on other sites

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

Br,

UEZ

Edited by UEZ

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Share on other sites

... 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 by PincoPanco

Chimp

small minds discuss people average minds discuss events great minds discuss ideas.... and use AutoIt....

Share on other sites

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

Edited by UEZ

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Create an account

Register a new account