Pattern 22 of 22
Bit Manipulation Pattern: Template + 194 LeetCode Problems
Use XOR, masks and the low-bit trick to replace whole data structures with an integer.
- Easy
- 40
- Medium
- 96
- Hard
- 58
What the bit manipulation pattern is
Bit manipulation problems reduce to a handful of identities that are worth knowing cold. XOR is its own inverse and is commutative, so xor-ing an entire array cancels every value that appears twice and leaves the one that does not — no hash map, no extra space. `x & (x - 1)` clears the lowest set bit, which counts set bits in as many iterations as there are ones rather than thirty-two, and instantly tests for a power of two. `x & -x` isolates that lowest set bit instead of clearing it. The second, larger use is the bitmask as a set: an integer's bits stand for membership, so a subset of up to twenty elements fits in one machine word, subsets can be enumerated by counting from zero to 2ⁿ, and a dynamic programming state can be indexed by which items have been used. Python integers have no fixed width and no overflow, which removes a whole class of bugs but also means a shift left never wraps and negative numbers behave as if they had infinitely many leading ones.
When to use it
- Every element appears a fixed number of times except one — XOR or per-bit counting finds it.
- The problem is about set bits, powers of two, or a specific bit position.
- n is at most about twenty and you need to iterate over subsets or track which items are used.
- A boolean set must be stored and compared cheaply, as a dynamic programming key.
The bit manipulation template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 194 problems listed below.
def single_number(nums):
"""Pairs cancel under XOR, so the odd one out survives."""
result = 0
for value in nums:
result ^= value
return result
def count_set_bits(x):
total = 0
while x:
x &= x - 1 # clears the lowest set bit, so this runs once per 1
total += 1
return totalComplexity characteristics
- Time
- O(n) for a scan, O(2ⁿ) for subset enumeration
- Auxiliary space
- O(1)
The XOR cancellation scan is one pass with a single accumulator: linear time, constant space, no hash map. Counting set bits with x & (x − 1) runs once per set bit rather than once per bit position, so it is O(popcount) instead of O(word size). Bitmask enumeration is O(2ⁿ) by definition and bitmask dynamic programming is O(2ⁿ·n), which is why these problems cap n at around twenty.
Eyes only
Meet the bit manipulation problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 194 bit manipulation LeetCode problems
Every problem in the library the bit manipulation pattern applies to, grouped by LeetCode's own difficulty rating. 173 of the 194 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (40)
Medium (96)
Hard (58)
Bit Manipulation pattern FAQ
What is the bit manipulation pattern?
Bit manipulation problems reduce to a handful of identities that are worth knowing cold. XOR is its own inverse and is commutative, so xor-ing an entire array cancels every value that appears twice and leaves the one that does not — no hash map, no extra space.
How many LeetCode problems use the bit manipulation pattern?
This page lists 194 LeetCode problems that the bit manipulation pattern applies to: 40 Easy, 96 Medium and 58 Hard. 173 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the bit manipulation pattern?
O(n) for a scan, O(2ⁿ) for subset enumeration time and O(1) space. The XOR cancellation scan is one pass with a single accumulator: linear time, constant space, no hash map. Counting set bits with x & (x − 1) runs once per set bit rather than once per bit position, so it is O(popcount) instead of O(word size). Bitmask enumeration is O(2ⁿ) by definition and bitmask dynamic programming is O(2ⁿ·n), which is why these problems cap n at around twenty.
When should I use the bit manipulation pattern in an interview?
Every element appears a fixed number of times except one — XOR or per-bit counting finds it. The problem is about set bits, powers of two, or a specific bit position.
Which bit manipulation problem should I start with?
LeetCode 67. Add Binary is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to bit manipulation?
Dynamic Programming, Hash Map, Backtracking, Math and Number Theory. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.