How to "reverse" a byte?

[Luis Babboni]

Hi people!

I want to know a fast way (if any) to go from for example:

00111011 to 11011100

in decimal (consider up numbers as UByte): from 220 to 59

Thanks!

[Tourist Trap]

The operator NOT maybe?

[Luis Babboni]

The operator NOT maybe?

Mmm, Not 220 = 35 = 11000100 <> 11011100 = 59

My need is to transform a a byte where less important bit is the lefter in "the same byte" but where the less important bit be the righter.

In other way: 12345678 in 87654321

[Luis Babboni]

I think is this discussion!! :-)

http://freebasic.net/forum/viewtopic.php?t=4726

[Luis Babboni]

I think is this discussion!! :-)

http://freebasic.net/forum/viewtopic.php?t=4726

It seems at least in 2006 there was not a fast way to do it.
I need it in a critical part of my chess engine code so I need that it be as fast as possible.

[fxm]

- For Byte:

Code: Select all

Function reverseByte (Byval b As Byte) As Byte
  Dim As String * 8 s = Str(Bin(b, 8))
  For I As Integer = 0 To 3
    Swap s[I], s[7-I]
  Next I
  Return Val("&b" & s)
End Function

- For Ubyte:

Code: Select all

Function reverseUbyte (Byval b As Ubyte) As Ubyte
  Dim As String * 8 s = Str(Bin(b, 8))
  For I As Integer = 0 To 3
    Swap s[I], s[7-I]
  Next I
  Return Val("&b" & s)
End Function

[Luis Babboni]

Thanks fxm!

But the target is to avoid loops.
Try to use bits operators.

for axample, for posible moves for the rook to left being the 8 occuped squares the 1s and 0s the free squares of the first byte and the 1 the position of the rook in the 2nd byte:

a: 11000101
b: 00000100

This simple operation: a Xor (a - 2*b) gives: 01111000 that is the desired result but for the opposite side I need to do (a´ Xor (a´ - 2*b´))´ being " ´ " the "swap" I talking.
https://chessprogramming.wikispaces.com ... ce+Attacks

[Luis Babboni]

...
for the opposite side I need to do (a´ Xor (a´ - 2*b´))´ being " ´ " the "swap" I talking.
...

Is the same like the other but "rotating the paper 180º".

[fxm]

You can also use a static internal lookup table that is built by opportunity on each new value (to avoid a long dead time of full initialization):

Code: Select all

Function reverseUbyte (Byval b As Ubyte) As Ubyte
  Static As Ubyte table(0 To 255)
  If b > 0 Andalso table(b) = 0 Then
    Dim As String * 8 s = Str(Bin(b, 8))
    For I As Integer = 0 To 3
      Swap s[I], s[7-I]
    Next I
    table(b) = Val("&b" & s)
  End if
  Return table(b)
End Function

[MrSwiss]

@fxm,

great stuff, as usual.
A lil' speed could be gained, by using UInteger (instead of Integer) as Loop-Counter.
(no sign checking needed)

[grindstone]

With 8 bits there are only 256 capabilities, so it would take a time next to none to initialize such a table once at the start of the program. In return you could avoid the If b > 0 Andalso table(b) = 0 Then at every access (you don't even need a Function):

Code: Select all

Dim Shared As String table
Dim As UByte reverse

table = String(256,Chr(0)) 'allocate the memory and fill with "0"s

'initialize the table
For x As Integer = 0 To 255
	For y As Integer = 0 To 7
		If Bit(x,y) Then
			table[x] = BitSet(table[x],7 - y)
		EndIf
	Next
Next

'test print
For x As Integer = 0 To 255
	reverse = table[x] 'get the reverse byte
	Print x, Bin(x,8), Bin(reverse,8)
Next

Sleep

[Luis Babboni]

Thanks to all!!

I like grindstone suggestion!
I´ll comment as soon as I work on it! :-)

[fxm]

Good.
I forgot the keyword BitSet!

[greenink]

The book here has many delightful bit hacks:
http://www.jjj.de/fxt/

[MrSwiss]

I also like grindstone's approach.
But, I don't see the reason for a String ...

Re-coded to use a UByte Array, added a Macro and using UInteger's as Loop-Counters:

Code: Select all

Dim As UByte table(255), reverse

#Define invByte(b)  ( table(b) )

'initialize the table
For x As UInteger = 0 To 255
    For y As UInteger = 0 To 7
        If Bit(x, y) Then
            table(x) = BitSet(table(x), 7 - y)
        Else
            table(x) = BitReset(table(x), 7 - y)
        EndIf
    Next
Next

'test print
For x As UInteger = 0 To 255
    reverse = invByte(x) 'get the reverse byte
    Print x, Bin(x, 8), Bin(reverse, 8)
Next

Sleep