Bit Hacks

Prev: 02-bentley-rules-for-optimizing-work Next: 04-assembly-language-computer-architecture

Binary Representation

Let $x=\{x_{w-1},x_{w-2},\dots ,x_0\}$ be a $w$-bit computer word.

So: 0b10010110 would represent 128 + 16 + 4 + 2 or 150 if it was unsigned.

The signed integer (two’s complement) would be:

$$x=(\sum _{k=1}^{w-2}{x}_k{2}^k)-x_{w-1}{2}^{w-1}$$

So: 0b10010110 would be -128 + 16 + 4 + 2 or -106.

Thus, 0b00000000 would be 0.

And 0b11111111 would be -1.

Thus, x + ~x = -1, or -x = ~x + 1.

C Bitwise Operators are:

• &: AND
• | OR
• ^ XOR
• ~ NOT
• << left shift
• >> right shift

Set the kth bit:

• Shift and OR: y = x | (1 << k)

Clear the kth bit: y = x & ~(1 << k)

Toggle the kth bit:

y = x ^ (1 << k)

Extract a bitfield from a word:

(x & mask) >> shift

Set a bitfield:

x = (x & ~mask) | (y << shift)

Swap without a temporary:

x = x ^ y;
y = x ^ y;
x = x ^ y;

Find the minimum of two integers:

if (x < y) r = x;
else r = y;

or

r = (x < y) ? x : y;

This requires a branch either way. We can do this without a branch:

r = y ^ ((x ^ y) & -(x < y));

However branchless paths can be worse than a compiler’s optimizations.

You can round up to a power of two:

uint32_t round_up_pow2(uint32_t v) {
    if (v == 0) return 1;
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;
}

You can use a debrujin sequence to compute log 2 of x if x is a power of 2:

int DEBRUIJN_IDX32[32] = {
    0,  1, 28,  2, 29, 14, 24,  3,
   30, 22, 20, 15, 25, 17,  4,  8,
   31, 27, 13, 23, 21, 19, 16,  7,
   26, 12, 18,  6, 11,  5, 10,  9
};
 
int log2_debruijn32(uint32_t x) {
    // Multiply by De Bruijn constant and use high 5 bits as index
    uint32_t idx = (x * 0x077CB531u) >> 27;
    return DEBRUIJN_IDX32[idx];
}

Population Count I

for (int r = 0; x !=0; r++)
	x &= x - 1;

Or you can use a lookup table:

int count[256] = { 0, 1, 1, 2, 1, 2, 2, 3 ..., 8};
for (int r = 0; x != 0; x >>= 8)
	r += count[x & 0xFF];

Prev: 02-bentley-rules-for-optimizing-work Next: 04-assembly-language-computer-architecture