How to "reverse" a byte?

New to FreeBASIC? Post your questions here.
Luis Babboni
Posts: 303
Joined: Mar 15, 2015 12:41

How to "reverse" a byte?

Postby Luis Babboni » Jan 17, 2017 21:34

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
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: How to "reverse" a byte?

Postby Tourist Trap » Jan 17, 2017 21:37

The operator NOT maybe?
Luis Babboni
Posts: 303
Joined: Mar 15, 2015 12:41

Re: How to "reverse" a byte?

Postby Luis Babboni » Jan 17, 2017 21:47

Tourist Trap wrote: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
Posts: 303
Joined: Mar 15, 2015 12:41

Re: How to "reverse" a byte?

Postby Luis Babboni » Jan 17, 2017 21:52

I think is this discussion!! :-)

http://freebasic.net/forum/viewtopic.php?t=4726
Luis Babboni
Posts: 303
Joined: Mar 15, 2015 12:41

Re: How to "reverse" a byte?

Postby Luis Babboni » Jan 17, 2017 21:58

Luis Babboni wrote: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
Posts: 9988
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: How to "reverse" a byte?

Postby fxm » Jan 17, 2017 22:17

- 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
Posts: 303
Joined: Mar 15, 2015 12:41

Re: How to "reverse" a byte?

Postby Luis Babboni » Jan 17, 2017 23:15

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
Posts: 303
Joined: Mar 15, 2015 12:41

Re: How to "reverse" a byte?

Postby Luis Babboni » Jan 18, 2017 1:32

Luis Babboni wrote:...
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
Posts: 9988
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: How to "reverse" a byte?

Postby fxm » Jan 18, 2017 8:32

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
Posts: 3634
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: How to "reverse" a byte?

Postby MrSwiss » Jan 18, 2017 11:00

@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
Posts: 755
Joined: May 05, 2015 5:35
Location: Germany

Re: How to "reverse" a byte?

Postby grindstone » Jan 18, 2017 11:24

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
Posts: 303
Joined: Mar 15, 2015 12:41

Re: How to "reverse" a byte?

Postby Luis Babboni » Jan 18, 2017 11:55

Thanks to all!!

I like grindstone suggestion!
I´ll comment as soon as I work on it! :-)
fxm
Posts: 9988
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: How to "reverse" a byte?

Postby fxm » Jan 18, 2017 12:16

Good.
I forgot the keyword BitSet!
greenink
Posts: 200
Joined: Jan 28, 2016 15:45

Re: How to "reverse" a byte?

Postby greenink » Jan 18, 2017 13:04

The book here has many delightful bit hacks:
http://www.jjj.de/fxt/
MrSwiss
Posts: 3634
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: How to "reverse" a byte?

Postby MrSwiss » Jan 18, 2017 13:22

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

Return to “Beginners”

Who is online

Users browsing this forum: No registered users and 7 guests