Bitwise Operations Deep Dive

Ten pieces past the operators themselves — the actual idioms built out of them, the ones that show up in register-manipulation code constantly enough to just memorize.

#define SET_BIT(x, n)    ((x) |= (1U << (n)))
#define CLEAR_BIT(x, n)  ((x) &= ~(1U << (n)))
#define TOGGLE_BIT(x, n) ((x) ^= (1U << (n)))
#define TEST_BIT(x, n)   (((x) >> (n)) & 1U)

All four follow the same shape: 1U << n builds a mask with only bit n set, then OR sets it, AND-with-NOT clears it, XOR flips it, and a shift-then-mask reads it back out.

A couple of the classic tricks

/* is n a power of 2? a power of 2 has exactly one bit set */
int is_power_of_2(unsigned int n) {
    return n && !(n & (n - 1));
}

/* Kernighan's bit-count: clears the lowest set bit each iteration */
int popcount(unsigned int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

n & (n-1) clears the lowest set bit — for a power of 2 that's the only set bit, so the result is 0. Kernighan's popcount just repeats that operation, counting how many times it takes to reach zero, which only loops once per set bit instead of once per bit in the whole word.

Endianness is the other half of this chapter — the same multi-byte value is stored lowest-byte-first (little-endian, x86) or highest-byte-first (big-endian) depending on the architecture, which matters the instant a struct gets serialized over a wire and read back on a different machine.