Bit manipulation: masks, shifts, and the n & (n-1) trick

Every integer is a row of bits

The number 13 is not really “thirteen” inside the machine — it is the bit pattern 1101 (8 + 4 + 0 + 1). Bit manipulation means operating on those individual bits directly, instead of on the number’s decimal value. The operators that do this are the bitwise operators, and there are exactly six worth memorizing.

The six operators

Before you can build anything useful, you need to know what each operator actually does to the bits — because mixing them up (using AND where OR belongs) is the most common source of subtle, hard-to-debug flag bugs. Each operator below acts on every bit position independently — bit i of the result depends only on bit i of the inputs.

• AND (&) — result bit is 1 only if both input bits are 1. Used to read or clear bits: 1100 & 1010 = 1000.
• OR (|) — result bit is 1 if either input bit is 1. Used to set bits: 1100 | 1010 = 1110.
• XOR (^) — result bit is 1 only if the input bits differ. Used to toggle bits and to find differences: 1100 ^ 1010 = 0110. XOR is its own inverse: x ^ y ^ y === x.
• NOT (~) — flips every bit (unary). ~1100 flips all bits, including the high ones you usually do not see.
• Left shift (<<) — slides bits left, filling with zeros on the right. 1 << 3 = 1000 (decimal 8). Each left shift by one multiplies by two.
• Right shift (>>) — slides bits right. 1101 >> 1 = 110 (decimal 6). Each right shift by one divides by two (toward negative infinity, because in most languages >> copies the sign bit).

Together, AND and OR handle reading and writing; XOR handles toggling and comparison; NOT inverts; the shifts scale. When you see a bit idiom in the wild, one of these six is always at its core.

The one-hot mask: the key building block

Almost every bit trick starts with a mask — a number whose bits select which positions you care about. The most useful mask is a single 1 shifted into position i: 1 << i. That gives a “one-hot” pattern with exactly one bit set, at position i. Combine it with an operator and you get the four idioms that do almost everything:

test  bit i:  (x >> i) & 1        ->  0 or 1
set   bit i:  x | (1 << i)        ->  forces bit i to 1
clear bit i:  x & ~(1 << i)       ->  forces bit i to 0
toggle bit i: x ^ (1 << i)        ->  flips bit i

To set a bit, OR with a mask that has that bit on. To clear a bit, AND with a mask that has that bit off (~(1 << i) is all ones except position i). To toggle, XOR with the one-hot mask. To test, shift the bit you want down to position 0 and mask off the rest with & 1. Four operators, one mask, every single-bit operation.

Classic 1: is n a power of two?

When you see a size or alignment check in a memory allocator or a hash-table resize, this trick is almost always hiding inside. A power of two has exactly one bit set: 1, 10, 100, 1000, ... (decimal 1, 2, 4, 8). Here is the trick that checks it in O(1) with no loop:

n & (n - 1) === 0      (for n > 0)

Why does it work? Subtracting 1 from a number flips its lowest set bit to 0 and turns every bit below it into 1. So 1000 - 1 = 0111. ANDing the two — 1000 & 0111 — has no bit in common, giving 0. If n had more than one bit set, the higher bits survive the AND and the result is non-zero. The n > 0 guard matters: 0 & (0 - 1) is also 0, but 0 is not a power of two.

Classic 2: counting set bits (Hamming weight)

The Hamming weight of a number is how many of its bits are 1. The naive way checks all 32 positions. Brian Kernighan’s algorithm is smarter: n &= n - 1 clears the lowest set bit (same n - 1 insight as above), so you loop once per set bit and stop the moment n hits zero:

count = 0
while n != 0:
    n &= n - 1      // erase the lowest set bit
    count += 1

A number with three set bits costs three iterations, not thirty-two. That makes the loop O(number of set bits) — cheaper than scanning every position when the number is sparse.