Hakmem 175 is probably the most famous example of bit bashing. In just nine PDP-10 instructions in calculates the next higher number with the same number of 1 bits. (Note that this can actually be done in eight PDP-10 instructions and one fewer variable, as described at the end of this page.) Unfortunately few people understand how it works, partly because the algorithm is subtle, and partly because few people today know the PDP-10 instruction set. The original item stated:
ITEM 175 (Gosper):
To get the next higher number (in A) with the same number of 1 bits: (A, B, C, D do not have to be consecutive)
MOVE B,A MOVN C,B AND C,B ADD A,C MOVE D,A XOR D,B LSH D,-2 IDIVM D,C IOR A,D
The code finds the lowest 1 bit with a 0 bit above and moves it one bit left, and then moves all the 1 bits to its right as far right as possible. To understand why this works, imagine numbering the 1 bits in the input and output from left to right. At least one 1 bit must move left, and to increase the number by as little as possible this should be the lowest 1 bit that can be moved one bit left. All the 1 bits to its right should then be moved as far right as possible in order to increase the number by as little as possible. In the syntax used in the Bit Bashing section of Safalra’s Website this becomes:
b = 0 - a
b = b & a
c = a + b
a = a ^ c
a = a >>> 2
a = a / b
a = a | c
This performs the algorithm described above in these stages:
- The first two lines set b to equal the highest 1 bit in a
- The next line sets c equal to the sum of a and b, moving left one bit the lowest 1 bit that can be moved left and removing the lower 1 bits
- The next line makes a contain one more 1 bit than the number of 1 bits in the lowest group of 1 bits in the original a
- The two lines move these 1 bits to the right, purposely losing two unrequired 1 bits in the process
- The last line sets a equal to c with the required number of 1 bits added at the right
On a RISC machine integer division is slow, but it can be replaced by a combination of shifts and jumps which runs much faster. The following example only works for 16-bit integers, but can easily be extended:
b = 0 - a
b = b & a
b = a + b
a = a ^ b
c = a & 0000000011111111
jump nonzero 4
a = a >>> 8
label 4
c = a & 0000000000001111
jump nonzero 2
a = a >>> 4
label 2
c = a & 0000000000000011
jump nonzero 1
a = a >>> 2
label 1
c = a & 0000000000000001
jump nonzero 0
a = a >>> 1
label 0
a = a >>> 2
a = a | b
Note that a renaming and reusing of variables in the original PDP-10 code yields a saving one of instruction (and one variable) over the Hakmem original:
MOVE B,A
MOVN C,B
AND C,B
ADD A,C
XOR B,A
LSH B,-2
IDIVM B,C
IOR A,B