Bit Manipulation
Intermediate · 14 min read · Problem-Solving Patterns, Greedy & Special Topics
XOR tricks, masks and counting bits — the handful that interviews use.
Bit manipulation feels like a bag of magic tricks, but interviews use only a handful of them — and each one follows from how binary numbers work. You need about six operators, three identities, and the confidence to look at a number as a row of 32 switches.
The operators
Java ints are 32-bit two's complement: -1 is all 1s, and >> copies the sign bit. When you loop over bits of a possibly negative number, use >>> or a fixed loop of 32 — otherwise n >> 1 on a negative number never reaches 0.
Single bits
Identity 1: n & (n − 1) clears the lowest set bit
Subtracting 1 turns the lowest 1-bit into 0 and every 0 below it into 1. AND-ing with n wipes all of them.
Identity 2: XOR cancels pairs
x ^ x = 0 and x ^ 0 = x, and XOR is commutative. XOR everything together and every pair cancels, leaving the odd one out:
Identity 3: count each bit position
XOR doesn't cancel triples. Instead, count how many numbers have each bit set: for the triples it's a multiple of 3, so any remainder belongs to the single number.
Other classics
XOR adds without carrying; AND finds where carries happen, shifted one place left. Repeat until there's nothing left to carry:
Bitmasks as subsets
For a set of n ≤ 20 items, the integers 0 … 2ⁿ − 1 represent every subset: bit i set means "item i is in the subset".
Practice ladder
Interview questions
- Why does n & (n − 1) clear the lowest set bit?
- How do you find the single number when every other number appears exactly twice, in O(1) space?
Further reading
Key takeaways
- Know the operators, and >> vs >>> for negative numbers.
- n & (n − 1) clears the lowest set bit: count bits, test powers of two.
- XOR cancels pairs: single number, missing number.
- Counting each bit position handles "appears k times".
- Bitmasks represent subsets of small sets and power bitmask DP; parenthesise bit expressions.