Bit Manipulation Pattern: Template + 194 LeetCode Problems

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 total

Complexity 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.

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 patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Bit Manipulation pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.