Operate directly on the binary representation of integers. Key operations: AND (&), OR (|), XOR (^), NOT (~), left shift (<<), right shift (>>). XOR is especially powerful: x ^ x = 0 and x ^ 0 = x. Used for toggling bits, counting set bits, and finding unique elements in O(1) space.
When to use this pattern
◆Find the single number that appears once (others appear twice)
◆Count set bits (Hamming weight)
◆Check if a number is a power of 2
◆Generate all subsets (bitmask enumeration)
◆Swap two numbers without a temp variable
Common patterns
XOR to find unique
XOR all elements. Pairs cancel; unique element remains.
n & (n-1) trick
Clears the lowest set bit. Count iterations to count bits.
Power of 2 check
n > 0 && (n & (n-1)) == 0 ← exactly one bit set.
Bitmask DP / subsets
Enumerate all 2ⁿ subsets with bitmask iteration.
Brute force → optimal thinking
Brute force
Use a HashMap to count occurrences → O(n) space.
Observation
XOR is its own inverse: identical bits cancel. Only the unique element survives.
Optimization
Single XOR pass over the array. No extra space needed.
Final complexity
O(n) time, O(1) space.
Quick Recall Check
What does a XOR a equal for any value a?
How do you clear the lowest set bit of n?
How do you check if n is a power of 2 in O(1)?
Am I ready to move on?
Check each question you can answer confidently before moving to the next topic.