Bit Manipulation

Bit Manipulation Patterns

Bit manipulation is a small topic with a high recognition threshold: the problems are easy once you know the trick and close to impossible if you do not. Nearly all of it rests on two ideas. XOR cancels a value with itself, which finds unpaired elements without any extra memory, and subtracting one from a number flips its lowest set bit and fills everything below it, which powers most of the remaining tricks.

2 patterns7 techniquesJava code

Where to start, and what comes next

01
XOR Tricks
The single number family. Start here, because the cancellation property is the most reused idea in the topic.
Single Number Find Missing Number Two Unique Numbers
02
Core Bit Tricks
Powers of two, counting bits, reversing and submask enumeration. Each is a one-line identity worth knowing on sight.
Power of 2 Check Count Set Bits (Hamming Weight)Reverse Bits Enumerate All Subsets of a Mask

If you only have time for three things

XOR cancelling pairs, and the extension that splits an array by one differing bit to find two unpaired values.
n AND n minus 1, which clears the lowest set bit and gives both the power-of-two test and Brian Kernighan's bit count.
x AND minus x, which isolates the lowest set bit, and why two's complement makes that work.

In an interview

Say the identity out loud before using it. Writing n & (n - 1) with no explanation reads as memorised; saying that subtracting one flips the lowest set bit and fills below it, so the AND clears exactly that bit, reads as understood. Also mention Integer.bitCount, since knowing the built-in exists and compiles to a single instruction is a point in its favour rather than against.

The idea underneath

Key tricks: n & (n-1) clears lowest set bit (power-of-2 check). XOR of all elements cancels pairs. Bit masks can represent subsets for DP. These are often O(1) space solutions.

Problems that use these patterns

Single NumberNumber of 1 BitsCounting BitsMissing NumberReverse BitsPower of Two

Questions people ask

Why does XOR find the single number?

Because a value XORed with itself is zero and anything XORed with zero is unchanged. XOR is also commutative, so the pairs cancel regardless of where they sit and only the unpaired value survives.

Why is the power-of-two test guarded against zero?

Zero passes it. Zero AND minus one is zero, which satisfies the check, but zero is not a power of two. The condition needs n greater than zero alongside it.

What is the submask enumeration trick for?

Iterating every subset of a bitmask, using s = (s - 1) AND mask. It is the basis of subset dynamic programming, and iterating every submask of every mask over n bits totals 3 to the n rather than 4 to the n, which is what makes those algorithms feasible.