[futurebasic] Re: [FB] Bit swapping

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : October 1999 : Group Archive : Group : All Groups

From: Robert Purves <robert.purves@...>
Date: Thu, 21 Oct 1999 13:13:30 +1300
>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).

Robert Purves

'---------------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
'----------------------------------------------------