Bit Manipulation Pattern — the interview skill nobody practices

Bit manipulation is writing code that operates on individual binary digits instead of whole numbers. Interview rounds test whether you recognize when a problem collapses to XOR, a mask, or a single bit check. The tricks are small; the recognition is the rep.

Bit manipulation is the pattern everyone skips — until it shows up in an interview and they freeze. Trace enough candidates through bit problems and the split is always the same: people who know the five tricks solve them in three minutes, and people who do not know them burn fifteen minutes reinventing XOR from scratch. CP-Algorithms' bit manipulation reference covers the formal derivations if you want the math, but for interviews you just need the five patterns below.

Diagram

Copy source

Rendering diagram...

The 5 Tricks

1. XOR to Find the Unique Element

a ^ a = 0, a ^ 0 = a, and XOR is commutative/associative. XOR-ing all elements cancels duplicates. Florian's XOR Trick writeup derives why this works from first principles — the key insight is that you can remove all pairs of duplicated values from a sequence of XOR operations without affecting the result.

PYTHON

Copy

def singleNumber(nums): result = 0 for n in nums: result ^= n return result

Solves Single Number (LC 136) in O(n) time, O(1) space. No hash map needed.

2. Bit Check / Set / Clear / Toggle

PYTHON

Copy

(n >> i) & 1 # is bit i set? n | (1 << i) # set bit i n & ~(1 << i) # clear bit i n ^ (1 << i) # toggle bit i

These four operations are the building blocks of everything else.

3. n & (n - 1) -- Clear the Lowest Set Bit

Removes the rightmost 1-bit. This is Brian Kernighan's algorithm — GeeksforGeeks explains it well: "subtracting 1 from a number flips all the bits after the rightmost set bit including the rightmost set bit itself." The beauty is that the loop runs only as many times as there are set bits:

PYTHON

Copy

def hammingWeight(n): count = 0 while n: n &= (n - 1) count += 1 return count

Only loops as many times as there are 1-bits.

4. n & (-n) -- Isolate the Lowest Set Bit

Returns a number with only the lowest set bit of n. This works because of two's complement representation — -n flips all bits and adds one, so the AND isolates exactly the bit where n and -n agree. Key to Single Number III (LC 260) where you partition elements by that bit to separate two unique numbers.

5. Power of Two Check

A power of two has exactly one bit set: n > 0 and (n & (n - 1)) == 0. Done.

When Interviewers Ask This

Bit problems test whether you know the tricks. If you do, they're fast. If you don't, you're stuck.

Most bit problems are easy or medium. They rarely appear as the hard problem in a loop. But I have watched candidates lose fifteen minutes on Single Number because they reached for a hash map instead of XOR — and then run out of time on the harder problem that actually mattered. As Educative's bit manipulation guide puts it, these techniques come up often enough in interviews that not knowing them is a real liability.

Recognition Signals

• The problem asks to find something "without extra space" -- bit tricks give O(1) space
• The problem involves powers of two, unique elements, or toggling states
• The interviewer says "can you do this in O(1) space?"
• Constraints mention 32-bit integers or bitwise operations explicitly

Common Mistakes

• Using a hash map when XOR works. If duplicates appear in pairs and you need the unique element, XOR is the move. A hash map works but misses the point — and the interviewer knows you missed it.
• Not tracing through a small example. If you are unsure about a bit operation, trace n = 6 (110 in binary) through the expression on paper. Takes ten seconds and saves you from the silent stare when the interviewer asks "are you sure about that?" I tell every candidate: trace before you commit.
• Overthinking. Bit problems reward pattern recognition, not creativity. Know the 5 tricks, apply the right one.

Practice Problems

1. Single Number (LC 136) -- XOR basics
2. Number of 1 Bits (LC 191) -- n & (n-1) trick
3. Reverse Bits (LC 190) -- bit-by-bit construction
4. Missing Number (LC 268) -- XOR with indices
5. Power of Two (LC 231) -- single-bit check
6. Counting Bits (LC 338) -- DP + lowest set bit

Sources

• NeetCode Bit Manipulation Roadmap — curated problem order
• LeetCode Bit Manipulation Tag — 180+ problems sorted by frequency
• Hacker's Delight (Henry S. Warren) — the definitive reference on bit tricks, if you want to go deeper
• Stanford Bit Twiddling Hacks — the canonical compendium of bit manipulation recipes