## Yet More Bit Hacks

### September 3, 2013

1. Counting parity: One approach counts the 1 bits, ignoring the 0 bits:

```unsigned int v; bool parity = false;```

``` ```

```while (v) {   parity = !parity;   v = v & (v - 1); }```

The other approach uses a byte-size table, here assembled with macros:

```static const bool ParityTable256 = { #   define P2(n) n, n^1, n^1, n #   define P4(n) P2(n), P2(n^1), P2(n^1), P2(n) #   define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)     P6(0), P6(1), P6(1), P6(0) };```

The parity of a byte can be determined directly, the parity of a word can be determined in two ways:

```unsigned int v; v ^= v >> 16; v ^= v >> 8; bool parity = ParityTable256[v & 0xff];```

or

```unsigned char * p = (unsigned char *) &v; parity = ParityTable256[p ^ p ^ p ^ p];```

If you only want to know the parity of a byte, and 64-bit arithmetic is available, you can distribute the byte’s bits through the available bits and compute the parity directly:

```unsigned char b; // byte value to compute the parity of bool parity =   (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;```

I rather like that one.

2. Reversing bits: The obvious solution copies bits from the input to the output; remember from previous exercises that CHAR_BIT is the number of bits in a character (normally 8):

```unsigned int v; // input bits to be reversed unsigned int r = v; // r will be reversed bits of v; first get LSB of v int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end```

``` unsigned int v; // input bits to be reversed unsigned int r = v; // r will be reversed bits of v; first get LSB of v int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end ```

```for (v >>= 1; v; v >>= 1) {   r <<= 1;   r |= v & 1;   s--; } r <<= s; // shift when v's highest bits are zero```

You can use table lookup if you’re willing to set aside 256 bytes for the table:

```static const unsigned char BitReverseTable256 = { #   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64 #   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16) #   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )     R6(0), R6(2), R6(1), R6(3) };```

As above, there are two solutions, one in integers and the other in characters:

```unsigned int v; // reverse 32-bit value, 8 bits at time unsigned int c; // c will get v reversed```

``` ```

```c = (BitReverseTable256[v & 0xff] << 24) |     (BitReverseTable256[(v >> 8) & 0xff] << 16) |     (BitReverseTable256[(v >> 16) & 0xff] << 8) |     (BitReverseTable256[(v >> 24) & 0xff]);```

or

```unsigned char * p = (unsigned char *) &v; unsigned char * q = (unsigned char *) &c; q = BitReverseTable256[p]; q = BitReverseTable256[p]; q = BitReverseTable256[p]; q = BitReverseTable256[p];```

There is also a method of reversing the bits of a byte using 64-bit operations:

`unsigned char b; // reverse this (8-bit) byte`

``` ```

`b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;`

3. Base-2 Logarithm: The base-2 logarithm of a 32-bit integer is the index of the highest set bit:

```unsigned int v; // 32-bit word to find the log base 2 of unsigned int r = 0; // r will be lg(v)```

``` ```

```while (v >>= 1) {   r++; }```

Table lookup is an obvious alternative:

```static const char LogTable256 = { #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n     -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,     LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),     LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7) };```

As in the other two exercises, there are two possibilities:

```unsigned int v; // 32-bit word to find the log of unsigned r; // r will be lg(v) register unsigned int t, tt; // temporaries```

``` ```

```if (tt = v >> 16) {   r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; } else {   r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; }```

or

```if (tt = v >> 24) {   r = 24 + LogTable256[tt]; } else if (tt = v >> 16) {   r = 16 + LogTable256[tt]; } else if (tt = v >> 8) {   r = 8 + LogTable256[tt]; } else {   r = LogTable256[v]; }```

You can see all these programs at work at http://programmingpraxis.codepad.org/mLbgPDHr.

Most of the solutions from the three exercises on bit hacks came from http://graphics.stanford.edu/~seander/bithacks.html.

Pages: 1 2

### One Response to “Yet More Bit Hacks”

1. David said

FORTH words to do this (64 bits)

```\ -- counting bits in 64 bit word --
: bitcount ( n -- n )
dup \$5555555555555555 and  swap \$AAAAAAAAAAAAAAAA and  1 rshift +
dup \$3333333333333333 and  swap \$CCCCCCCCCCCCCCCC and  2 rshift +
dup \$0F0F0F0F0F0F0F0F and  swap \$F0F0F0F0F0F0F0F0 and  4 rshift +
dup \$00FF00FF00FF00FF and  swap \$FF00FF00FF00FF00 and  8 rshift +
dup \$0000FFFF0000FFFF and  swap \$FFFF0000FFFF0000 and 16 rshift +
dup \$00000000FFFFFFFF and  swap \$FFFFFFFF00000000 and 32 rshift + ;

: parity ( n -- n )
bitcount 1 and ;

\ -- reverse bits in 64 bit word --
: reversebits ( n -- n )
dup  1 rshift \$5555555555555555 and  swap \$5555555555555555 and  1 lshift  or
dup  2 rshift \$3333333333333333 and  swap \$3333333333333333 and  2 lshift  or
dup  4 rshift \$0F0F0F0F0F0F0F0F and  swap \$0F0F0F0F0F0F0F0F and  4 lshift  or
dup  8 rshift \$00FF00FF00FF00FF and  swap \$00FF00FF00FF00FF and  8 lshift  or
dup 16 rshift \$0000FFFF0000FFFF and  swap \$0000FFFF0000FFFF and 16 lshift  or
dup 32 rshift                        swap                       32 lshift  or ;

\ log of unsigned integer (log -1 == 63), also lowbit (find lowest bit set)

create convert64
0 c,  1 c, 48 c,  2 c, 57 c, 49 c, 28 c,  3 c,
61 c, 58 c, 50 c, 42 c, 38 c, 29 c, 17 c,  4 c,
62 c, 55 c, 59 c, 36 c, 53 c, 51 c, 43 c, 22 c,
45 c, 39 c, 33 c, 30 c, 24 c, 18 c, 12 c,  5 c,
63 c, 47 c, 56 c, 27 c, 60 c, 41 c, 37 c, 16 c,
54 c, 35 c, 52 c, 21 c, 44 c, 32 c, 23 c, 11 c,
46 c, 26 c, 40 c, 15 c, 34 c, 20 c, 31 c, 10 c,
25 c, 14 c, 19 c,  9 c, 13 c,  8 c,  7 c,  6 c,

: (ulog)  ( n -- n )  \ use only when n is a power of two.
\$3F79D71B4CB0A89 * 58 rshift convert64 + c@ ;

: lowbit  ( n -- n )
dup negate and (ulog) ;

: ulog   ( n -- n )
dup 1  rshift or
dup 2  rshift or
dup 4  rshift or
dup 8  rshift or
dup 16 rshift or
dup 32 rshift or
dup 1 rshift - (ulog) ;
```

Usage examples:

```1000 ulog . 9  ok
9 parity . 0  ok
254 parity . 1  ok
hex  ok
FFFF0000FFFF reversebits u. FFFF0000FFFF0000  ok
```