FB II Compiler

PG PRO

Debugging

Memory

System

Mathematics

Resources

Disk I/O

Windows

Controls

Menus

Mouse

Keyboard

Text

Fonts

Drawing

Sound

Clipboard

Printing

Communication

ASM

Made with FB

FB II COMPILER

Swap bits


What would be the fastest way to swap eight bits, so that e.g. 64 becomes 2 (01000000 <> 00000010) and 192 becomes 3 (11000000 <> 00000011)?

Instead of special-purpose 8-bit reversal code, consider a general purpose FN, able to reverse 16- or 32-bit variables as well. FN BitRev in the program below illustrates a powerful programming technique for such tasks: recursion. BitRev splits the original number into two halves, bit-reverses each half (by calling itself recursively), and re-assembles the halves in reverse order.

Then, for speed, consider another powerful technique: a look-up table. This is useful when some function is expensive to compute but has a manageable number of possible input values. For 8-bit reversals, there are only 256 possible inputs, whose "outputs" can conveniently be pre-computed and kept in gReversedByteArray(). The program shows a huge speed increase (at least 50X) from this technique, by timing a million calculations and a million look-ups. Times are reported in ticks (=1/60s).
'---------------A complete FB2 or FB^3 program----------------
DIM gReversedByteArray(255)
END GLOBALS

' register on' uncomment for FB^3

LOCAL FN BitRev(num&, nBits) ' nBits should be 2,4,8,16 or 32
  DIM left&, right&, mask&
  nBits = (nBits>>1)
  mask& = BIT(nBits)-1
  right& = num& AND mask&
  left& = (num& >> nBits) AND mask&
  LONG IF nBits>1' recursion limit
    right& = FN BitRev(right&, nBits)
    left& = FN BitRev(left&, nBits)
  END IF
END FN = (right& << nBits) OR left&

LOCAL FN InitReverseByteArray
  DIM j
  FOR j=0 TO 255
    gReversedByteArray(j) = FN BitRev(j,8)
  NEXT
END FN

DIM b&, rb&, j&, ticks&, nBits
WINDOW 1,"",(0,0)-(620,300)
DEFSTR LONG
' test 8-byte reversal
b&=123: rb& = FN BitRev(b&, 8)
PRINT "8-bit " RIGHT$(BIN$(b&),8) " --> " RIGHT$(BIN$(rb&),8)

' test 16-bit reversal
b&=12301: rb&=FN BitRev(b&, 16)
PRINT "16-bit "RIGHT$(BIN$(b&),16) " --> " RIGHT$(BIN$(rb&),16)

' test 32-bit reversal
b&=-1230000101: rb&=FN BitRev(b&, 32)
PRINT "32-bit " RIGHT$(BIN$(b&),32) " --> " RIGHT$(BIN$(rb&),32)

_numTotest=1000000
PRINT "Speed test " _numTotest " 8-bit reversals..."
ticks& = FN TICKCOUNT
FOR j&=1 TO _numTotest
  rb& = FN BitRev(123, 8) ' calculate
NEXT
ticks& = FN TICKCOUNT - ticks&
PRINT RIGHT$(BIN$(123),8) " --> " RIGHT$(BIN$(rb&),8)
PRINT "Calculation ticks =" ticks&

FN InitReverseByteArray ' pre-compute table

ticks& = FN TICKCOUNT
FOR j&=1 TO _numTotest
  rb& = gReversedByteArray(123) ' look-up
NEXT
ticks& = FN TICKCOUNT - ticks&
PRINT RIGHT$(BIN$(123),8) " --> " RIGHT$(BIN$(rb&),8)
PRINT "Look-up table ticks =" ticks&

DO: HANDLEEVENTS: UNTIL FN BUTTON
'----------------------------------------------------
Robert Purves

I remember asking...

What would be the fastest way to swap eight bits, so that e.g. 64 becomes 2 (01000000 <> 00000010) and 192 becomes 3 (11000000 <> 00000011)?

... and then I thought:
'Split the byte in half, and make a lookup-table of inverted
'4-bit numbers, e.g. f(7) = 14, because 0111 <> 1110

DIM f(15)
DATA 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15
FOR i = 0 TO 15
  READ f(i)
NEXT

'Then twiddle the bits of the two halves of the byte, e.g. if our byte is a = 26 = &1A

  a  = &1A
  b1 = a  /  16               'b1 = &1
  b2 = a MOD 16               'b2 = &A
  c  = 16 * f(b2) + f(b1)              ' c = 16 * 5 + 8 = &58

'Which gives the reversed byte in c.
How's that? It seems about midway between the two beautiful suggestions Robert Purves made, doesn't it?
Now, there should be a way to find the reverses without recourse to a lookup-table...
Hans van Maanen

Now, there should be a way to find the reverses without recourse to a lookup-table...

But why? Your table only needs 16 entries--just 16 bytes if you use a BYTE array. If you don't want the minimal overhead of an array, just use a 16-byte var and do this:
DIM swapList;16
'set values
then
swappedNybble% = PEEK (@swapList + nybbleVal)
Doing anything else will use more mem than that for code, and be slower.

BTW, I think bitshifts would be faster for the calcs you showed:
  a  = &1A
  b1 = a >> 4              'b1 = &1
  b2 = a AND 15            'b2 = &A
  c  = f(b2) << 4 + f(b1)              ' c = 16 * 5 + 8 = &58
Now, there should be a way to find the reverses without recourse to a lookup-table...

try this:
LOCAL FN swapNybble%(nybble%)
 select nybble%
  case 0,6,9,15    '= no change
  case 1,8: nybble% = nybble% XOR 9
  case 2,4: nybble% = nybble% XOR 6
  case else:nybble% = nybble% XOR 15
 end select
END FN = nybble% AND 15

  a  = &1A
  swappedVal% = FN swapNybble%(a>>4) OR FN swapNybble%(a AND 15) << 4
At least it's a different approach.
Jay

And then I, too, thought: "What about BetterBitRev?"
'---------------A complete FB2 or FB^3 program----------------
END GLOBALS

' register on' uncomment for FB^3

LOCAL FN BetterBitRev(num&, nBits)
DIM out&,j
out& = 0
FOR j = 1 TO nBits
out& = (out&<<1) OR (num& AND 1)
num& = num&>>1
NEXT
END FN = out&

DIM b&, rb&
WINDOW 1,"",(0,0)-(620,300)

DEFSTR LONG
' test 8-byte reversal
b&=123: rb& = FN BetterBitRev(b&, 8)
PRINT "8-bit " RIGHT$(BIN$(b&),8) " --> " RIGHT$(BIN$(rb&),8)

' test 16-bit reversal
b&=12301: rb&=FN BetterBitRev(b&, 16)
PRINT "16-bit "RIGHT$(BIN$(b&),16) " --> " RIGHT$(BIN$(rb&),16)

' test 32-bit reversal
b&=-1230000101: rb&=FN BetterBitRev(b&, 32)
PRINT "32-bit " RIGHT$(BIN$(b&),32) " --> " RIGHT$(BIN$(rb&),32)

DO: HANDLEEVENTS: UNTIL FN BUTTON
Robert Purves