## 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[256] =`

{

# 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[0] ^ p[1] ^ p[2] ^ p[3]];

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[256] =`

{

# 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[3] = BitReverseTable256[p[0]];

q[2] = BitReverseTable256[p[1]];

q[1] = BitReverseTable256[p[2]];

q[0] = BitReverseTable256[p[3]];

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[256] =`

{

#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.

FORTH words to do this (64 bits)

Usage examples: