Bit Manipulation: when to spot it, explain it, and practice it
Bit manipulation is most useful when the problem really lives at the level of binary state: toggles, subsets, parity, masks, or compact transitions. The trick is to know when bits simplify the model rather than make it look clever.
Pattern coverage
30+
Best first move
Choose whether bits represent membership, parity, or state flags.
Common failure point
Using bit tricks without a clean model behind them.
When this pattern should come to mind
Checklist before you code
The solving flow that works well in interviews
Define what each bit means.
Pick the one operation that naturally updates that meaning.
Use masks to compress repeated state if n is small enough.
Check one or two hand-worked examples.
Keep the final code explainable in plain language.
Common variants
Unique-number logic
Use XOR to cancel duplicates and isolate the answer.
Bitmask enumeration
Represent a subset or configuration as bits.
Bit DP / transitions
Use masks as DP states when the dimension is small.
Template preview
x & (x - 1) # clear lowest set bit
x & -x # isolate lowest set bit
x | (1 << i) # set bit i
x & ~(1 << i) # clear bit i
x ^ (1 << i) # toggle bit i
(x >> i) & 1 # read bit i
Classic problems with useful framing
#136
Single Number
The cleanest XOR cancellation problem.
Find the element that appears once when all others appear twice.
#338
Counting Bits
Good for mixing DP intuition with bit tricks.
For every number from 0 to n, count how many set bits it has.
#371
Sum of Two Integers
Useful for explaining XOR and carry separation.
Compute a + b without using + or -.
#78
Subsets
A simple bridge from recursion to bitmask enumeration.
Return all possible subsets of the given array.
A more useful problem ladder for practice
This is not a random list. It is ordered to help candidates build recognition first, add key variants next, and then increase pressure with harder cases.
Foundation
#136 Single Number
Find the element that appears once when all others appear twice.
a ^ a = 0 and a ^ 0 = a, so order does not matter.
Foundation
#338 Counting Bits
For every number from 0 to n, count how many set bits it has.
bits[i] = bits[i & (i - 1)] + 1 is the cleanest recurrence.
Variant depth
#371 Sum of Two Integers
Compute a + b without using + or -.
Sum = XOR, carry = (AND << 1). Repeat until carry is zero.
High-frequency mistakes
Using bit tricks without a clean model behind them.
Forgetting operator precedence in mixed expressions.
Ignoring sign issues in languages with fixed-width integers.
Overcomplicating a problem that would be simpler with arrays or sets.
Recommended practice path
Start with single number and counting bits.
Then solve sum without plus and subset enumeration.
Add simple bitmask DP after that.
Finish with harder compression problems only when the basics feel natural.