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

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 specialpurpose 8bit reversal code, consider a general purpose FN, able to reverse 16 or 32bit 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, bitreverses each half (by calling itself recursively), and reassembles the halves in reverse order.
Then, for speed, consider another powerful technique: a lookup table. This is useful when some function is expensive to compute but has a manageable number of possible input values. For 8bit reversals, there are only 256 possible inputs, whose "outputs" can conveniently be precomputed 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 lookups. 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 8byte reversal
b&=123: rb& = FN BitRev(b&, 8)
PRINT "8bit " RIGHT$(BIN$(b&),8) " > " RIGHT$(BIN$(rb&),8)
' test 16bit reversal
b&=12301: rb&=FN BitRev(b&, 16)
PRINT "16bit "RIGHT$(BIN$(b&),16) " > " RIGHT$(BIN$(rb&),16)
' test 32bit reversal
b&=1230000101: rb&=FN BitRev(b&, 32)
PRINT "32bit " RIGHT$(BIN$(b&),32) " > " RIGHT$(BIN$(rb&),32)
_numTotest=1000000
PRINT "Speed test " _numTotest " 8bit 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 ' precompute table
ticks& = FN TICKCOUNT
FOR j&=1 TO _numTotest
rb& = gReversedByteArray(123) ' lookup
NEXT
ticks& = FN TICKCOUNT  ticks&
PRINT RIGHT$(BIN$(123),8) " > " RIGHT$(BIN$(rb&),8)
PRINT "Lookup 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 lookuptable of inverted
'4bit 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 lookuptable...
Hans van Maanen
Now, there should be a way to find the reverses without recourse to a lookuptable...
But why? Your table only needs 16 entriesjust 16 bytes if you use a BYTE array. If you don't want the minimal overhead of an array, just use a 16byte 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 lookuptable...
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 8byte reversal
b&=123: rb& = FN BetterBitRev(b&, 8)
PRINT "8bit " RIGHT$(BIN$(b&),8) " > " RIGHT$(BIN$(rb&),8)
' test 16bit reversal
b&=12301: rb&=FN BetterBitRev(b&, 16)
PRINT "16bit "RIGHT$(BIN$(b&),16) " > " RIGHT$(BIN$(rb&),16)
' test 32bit reversal
b&=1230000101: rb&=FN BetterBitRev(b&, 32)
PRINT "32bit " RIGHT$(BIN$(b&),32) " > " RIGHT$(BIN$(rb&),32)
DO: HANDLEEVENTS: UNTIL FN BUTTON
Robert Purves
