14 Bit Manipulation Problems to Master for Coding Interviews

Bit manipulation has a reputation for being a bag of disconnected tricks. It isn't. Every bit manipulation problem comes down to five underlying moves, and once you see those moves, even the hard problems start to feel like applications of the same four or five lines.

The first time you see n & (n-1) your reaction is: what? The second time, you get it. The third time, you wonder how you ever solved popcount problems without it. That's the whole arc.

Do them in order. The later ones build on the earlier ones.

Five Patterns, Fourteen Bit Manipulation Problems

Every problem below belongs to one of five families:

n & (n-1) clears the lowest set bit. Popcount, power-of-two checks, and DP on bit structure all use it.
XOR cancellation. x ^ x == 0 and x ^ 0 == x. Pairs cancel. Singletons survive.
Bit arithmetic. Adding, reversing, and masking without using operators.
Bitmask encoding. Compress a small set (26 letters, n items) into a single integer. Membership check becomes AND.
Bitmask as state. Represent "which nodes have been visited" or "which items have been chosen" as a bitmask. Powers BFS and DP on exponential-but-bounded state spaces.

The `n & (n-1)` Trick Clears One Bit at a Time

n & (n-1) does exactly one thing: flips the lowest set bit to zero. That's it. Looks like cursed code. Actually, it is not. Subtracting 1 from a number flips the lowest set bit off and flips everything below it on. AND-ing with the original nukes those flipped bits and leaves everything above untouched. One operation, one fewer set bit.

Binary diagram showing n=12 (1100) AND n-1=11 (1011) equals 8 (1000), with the lowest set bit cleared

That one operation powers three separate interview problems.

1. Number of 1 Bits (LC 191) · Easy

Count the set bits in a 32-bit integer. The naive approach loops 32 times and checks the LSB each time. The faster approach uses n & (n-1) to skip zeros: each iteration eliminates one set bit, so the loop runs exactly as many times as there are 1s.

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= n - 1  # clear the lowest set bit
        count += 1
    return count

This is Brian Kernighan's algorithm. Python's bin(n).count('1') and Java's Integer.bitCount(n) implement it internally. Know the trick behind the built-in.

2. Counting Bits (LC 338) · Easy

Return an array ans where ans[i] is the popcount of i, for all i from 0 to n. You could call hammingWeight n times. The smarter approach notices that every number shares all but its lowest bit with a smaller number you already computed.

def countBits(n: int) -> list[int]:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

i >> 1 is i with its LSB dropped. You've already counted those bits. Add 1 if the dropped bit was 1. Pure DP, O(n) total.

3. Power of Two (LC 231) · Easy

A power of two has exactly one set bit: 1, 10, 100, 1000 in binary. If a number has exactly one set bit, clearing it produces zero. So n > 0 and n & (n-1) == 0 is the entire solution.

def isPowerOfTwo(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

The n > 0 guard is non-optional. 0 & -1 == 0 in Python, which would otherwise give a false positive for zero. Yes, interviewers will test zero. They always do.

XOR Cancels Pairs. Everything Else Survives.

XOR is commutative, associative, and self-inverse. XOR a value with itself and you get zero. XOR a value with zero and you get the value back. Those two properties together mean: XOR over a multiset leaves only the elements that appear an odd number of times.

This is either deeply elegant or deeply suspicious, depending on your mood. It's the same operation your CPU uses to zero registers. It erases duplicates like they were never there.

4. Single Number (LC 136) · Easy

Every element appears twice except one. XOR everything: pairs cancel to zero, the singleton comes out the other end.

def singleNumber(nums: list[int]) -> int:
    result = 0
    for n in nums:
        result ^= n
    return result

O(n) time, O(1) space. One pass. No hash map needed. Show this to a non-programmer and they will not believe you.

5. Missing Number (LC 268) · Easy

An array of n distinct numbers from 0 to n, with one missing. XOR all indices with all values. Each present number cancels its matching index. The missing number's index has no partner, so it survives.

def missingNumber(nums: list[int]) -> int:
    result = len(nums)  # start with n (the last "expected" index)
    for i, n in enumerate(nums):
        result ^= i ^ n
    return result

There's a sum formula that also works (n*(n+1)//2 - sum(nums)). The XOR version shows you understand the cancellation pattern, not just the formula. Interviewers notice the difference.

6. Hamming Distance (LC 461) · Easy

Hamming distance between two integers is the number of bit positions where they differ. XOR produces a 1 at every position where the bits differ. So Hamming distance is the popcount of x ^ y.

def hammingDistance(x: int, y: int) -> int:
    return bin(x ^ y).count('1')

Two-step composition: XOR as a diff, then count the 1s. This composition appears in harder problems too.

7. Single Number III (LC 260) · Medium

Two unique numbers appear once each; everything else appears twice. XOR everything to get xor_ab = a ^ b. You can't separate them directly since you'd need to know a or b. The rightmost set bit of xor_ab is a position where a and b disagree. Use it to split the array into two groups that each contain exactly one of the two unique numbers, then XOR each group.

def singleNumber(nums: list[int]) -> list[int]:
    xor_ab = 0
    for n in nums:
        xor_ab ^= n

    diff_bit = xor_ab & (-xor_ab)  # isolate lowest set bit

    a = 0
    for n in nums:
        if n & diff_bit:
            a ^= n
    return [a, xor_ab ^ a]

The expression xor_ab & (-xor_ab) isolates the lowest set bit. That's a pattern worth memorizing: it shows up in Fenwick trees too.

Bit Arithmetic: When You Can't Use the Operators

Some problems prohibit + and - directly. Others use bit arithmetic as the natural tool to reveal structure. The Sum of Two Integers problem (problem 9) is a rite of passage: you spend ten minutes rediscovering how a CPU adder works and come out the other end with a new appreciation for hardware engineers.

8. Reverse Bits (LC 190) · Easy

Reverse the bits of a 32-bit unsigned integer. Extract the LSB, place it at the MSB end of the result, then shift both values. Repeat 32 times.

def reverseBits(n: int) -> int:
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

Each iteration takes the rightmost bit of n and appends it to the left of result. After 32 iterations, result holds the mirror image.

9. Sum of Two Integers (LC 371) · Medium

Add two integers without using + or -. XOR gives the per-bit sum ignoring carry. AND shifted left gives the carry. Repeat until carry is zero.

def getSum(a: int, b: int) -> int:
    mask = 0xFFFFFFFF
    while b & mask:
        carry = (a & b) << 1
        a = a ^ b
        b = carry
    return a if b == 0 else a & mask

Python's arbitrary-precision integers mean negative numbers need the 32-bit mask treatment. The core loop: partial sum via XOR, carry via AND shift, converge to zero carry. This is exactly what a hardware half-adder does. Your interviewer probably does not expect you to know that, but you do now.

10. Bitwise AND of Numbers Range (LC 201) · Medium

Find the bitwise AND of all integers from left to right inclusive. Brute-forcing the range times out. The answer is the common bit prefix of left and right. Any bit where they differ will have flipped at least once across the range, contributing a zero in the AND.

def rangeBitwiseAnd(left: int, right: int) -> int:
    shift = 0
    while left != right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift

Shift both right until they're equal. That strips the differing suffix. Shift the result back to the original scale. The insight is that a range traversal zeros out all bits below the common prefix.

A Bitmask Is a Set in Disguise

When the universe is small (26 letters, n items up to 20), you can represent an entire set as a single integer. Bit i is set if element i is in the set. Membership is mask & (1 << i). Union is |. Intersection is &. This turns O(k) set operations into O(1) integer operations.

The first time this clicks, it feels like cheating.

11. Maximum Product of Word Lengths (LC 318) · Medium

Find the maximum len(a) * len(b) over all pairs of words that share no letters. Checking every pair of letters directly is O(n^2 * 26). Encode each word as a 26-bit integer where bit i is set if the i-th letter of the alphabet appears. Two words share no letters if and only if their masks AND to zero.

def maxProduct(words: list[str]) -> int:
    masks = []
    for word in words:
        mask = 0
        for ch in word:
            mask |= 1 << (ord(ch) - ord('a'))
        masks.append(mask)

    best = 0
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            if masks[i] & masks[j] == 0:
                best = max(best, len(words[i]) * len(words[j]))
    return best

Building the masks is O(total characters). Each pairwise check is O(1). The 26-bit alphabet mask recurs any time you need "do these two things share any character" in O(1).

12. Subsets (LC 78) · Medium

Return all subsets of an array of distinct integers. Backtracking works, but so does a bitmask enumeration. Each integer from 0 to 2^n - 1 is a bitmask where bit j being set means "include nums[j] in this subset."

def subsets(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = [nums[j] for j in range(n) if mask & (1 << j)]
        result.append(subset)
    return result

O(n * 2^n) time and space, same as backtracking. The bitmask version is iterative and shorter, and it teaches the connection between integers and subsets that makes bitmask DP legible when you get to it.

When the State Space Is the Bitmask

These two problems use bitmasks not as encodings of individual items, but as components of a search algorithm's state. The bitmask represents "what has been visited" or "what has been chosen," and you run BFS or DP over (current_node, visited_mask) pairs. If a problem says n ≤ 12, this is probably why.

13. Maximum XOR of Two Numbers in an Array (LC 421) · Medium

Find the maximum nums[i] XOR nums[j]. Brute force is O(n^2). The greedy approach builds the answer bit by bit from the most significant bit: at each position, try setting that bit to 1 and check whether any two number prefixes in the array can produce that XOR.

def findMaximumXOR(nums: list[int]) -> int:
    max_xor = 0
    mask = 0
    for i in range(31, -1, -1):
        mask |= (1 << i)
        prefixes = {num & mask for num in nums}
        candidate = max_xor | (1 << i)
        # if p1 ^ p2 == candidate, then p1 ^ candidate == p2
        if any((candidate ^ p) in prefixes for p in prefixes):
            max_xor = candidate
    return max_xor

The check works because p1 ^ p2 == candidate is equivalent to p1 ^ candidate == p2. So for each prefix, check whether its XOR-partner exists in the prefix set. O(n * 32) overall.

A binary trie is the other standard approach: insert all numbers and greedily walk the trie choosing the opposite bit at each level. Both are O(n * 32). The prefix-set approach is faster to code under pressure.

14. Shortest Path Visiting All Nodes (LC 847) · Hard

An undirected graph of at most 12 nodes. Find the shortest walk that visits every node. Nodes and edges may be revisited. The n ≤ 12 constraint is the signal: state space is n * 2^n = 12 * 4096 = 49,152 states. Tractable with BFS. Without the constraint, this is TSP, which is NP-hard, which means your interviewer either loves you or is testing whether you panic.

Encode state as (current_node, visited_bitmask). Run multi-source BFS starting from all nodes simultaneously. The first state where visited == (1 << n) - 1 gives the minimum steps.

from collections import deque

def shortestPathLength(graph: list[list[int]]) -> int:
    n = len(graph)
    if n == 1:
        return 0
    full = (1 << n) - 1
    visited = set()
    queue = deque()

    for i in range(n):
        state = (i, 1 << i)
        queue.append((state, 0))
        visited.add(state)

    while queue:
        (node, mask), steps = queue.popleft()
        for neighbor in graph[node]:
            new_mask = mask | (1 << neighbor)
            if new_mask == full:
                return steps + 1
            state = (neighbor, new_mask)
            if state not in visited:
                visited.add(state)
                queue.append((state, steps + 1))

    return -1

Multi-source BFS starts all nodes at step 0 because the problem doesn't fix a start or end. BFS guarantees the first time you reach full, it's the shortest path. This is bitmask BFS, and the same pattern underlies TSP-style DP (the Held-Karp algorithm runs in O(n^2 * 2^n) using the same state representation).

For the BFS mechanics, see BFS pattern recognition.

Why This Order Works

The sequence is intentional. You can't reason about problem 7 (Single Number III) without the cancellation property you ingrained in problems 4-6. You can't write problem 14 without understanding the bitmask-as-state idea you first saw in problem 12.

Do all 14, in order, without looking at hints. If you get stuck on problem 7, go back to 4 and re-derive why XOR cancels pairs. The understanding compounds.

Once you've done all 14, read the five core bit manipulation patterns to see how they map to problem-recognition signals. The patterns article tells you which trick to reach for; this list gives you the muscle memory to execute.

If you want to practice explaining these problems out loud rather than just coding them silently, SpaceComplexity runs voice-based mock interviews where you reason through problems with an AI interviewer in real time. Bit manipulation problems are trivial to solve in your head and surprisingly painful to narrate clearly. The gap shows up fast.

Key Takeaways

n & (n-1) clears the lowest set bit. Use it for popcount, power-of-two detection, and DP indexed by bits.
n & -n isolates the lowest set bit. Appears in Single Number III, Fenwick trees, and anywhere you need to split a group by a differing bit.
XOR cancels pairs. If something appears an odd number of times in a multiset, XOR the whole thing and it comes out.
Bitmask encoding turns small-alphabet membership into O(1) AND checks. 26 letters fits in one int.
When n ≤ 20, ask whether a bitmask DP or BFS fits. State space is at most 20 * 2^20 = ~20M. Usually fine.
Sum without +: XOR is partial sum, (a & b) << 1 is carry, repeat until carry is zero.
Greedy prefix XOR (problem 13) and bitmask BFS (problem 14) are the two hard patterns. Both require having internalized the simpler problems first.