Bit Manipulation

Why bits deserve their own chapter

Bit manipulation has a reputation as an obscure parlor trick. It isn't. It's a small, closed vocabulary — maybe eight primitives — that unlocks a specific category of problems where every other approach wastes space or time. The tell is almost always one of these:

• "Find the element that appears an odd number of times."
• "Count the set bits in a number" (or sum them across many numbers).
• "Enumerate all subsets of a set."
• "Check if something is a power of two."
• "Toggle/set/clear a flag."

See one of those shapes, reach for bits. The vocabulary follows.

The four operations and what they actually do

Let's make this concrete. Take two 8-bit numbers and trace through each operation:

a = 0b10110100  (180)
b = 0b01101110  (110)

flowchart TD
    subgraph AND["AND: 1 only if both are 1"]
        direction LR
        A1["10110100"] --- OP1["&"] --- A2["01101110"] --> R1["00100100  (36)"]
    end
    subgraph OR["OR: 1 if either is 1"]
        direction LR
        A3["10110100"] --- OP2["|"] --- A4["01101110"] --> R2["11111110  (254)"]
    end
    subgraph XOR["XOR: 1 if exactly one is 1"]
        direction LR
        A5["10110100"] --- OP3["^"] --- A6["01101110"] --> R3["11011010  (218)"]
    end
    subgraph NOT["NOT: flip every bit"]
        direction LR
        A7["10110100"] --- OP4["~"] --> R4["01001011  (75)"]
    end
    style R1 fill:#7c5cff,color:#fff
    style R2 fill:#22d3ee,color:#0a0a0f
    style R3 fill:#00ff9d,color:#0a0a0f
    style R4 fill:#ff4d8d,color:#fff

AND is a mask — it keeps only the bits you care about. OR turns bits on. XOR flips bits, and has the special property that a ^ a = 0. NOT flips everything (and in two's complement, ~n = -n - 1).

Then there are shifts: n << k multiplies by 2ᵏ (shift bits left, fill zeros on right); n >> k divides by 2ᵏ (shift right, fill with sign bit in most languages). Shifts are how you construct masks: 1 << i gives you a number with only bit i set.

The four bit-position primitives

Everything else builds on these. Burn them in:

Operation	Code	What it does
Check bit i	(n >> i) & 1	1 if bit i is set, 0 otherwise
Set bit i	n | (1 << i)	Forces bit i to 1
Clear bit i	n & ~(1 << i)	Forces bit i to 0
Toggle bit i	n ^ (1 << i)	Flips bit i

The mechanics of check: right-shift n by i positions, bringing bit i to position 0, then AND with 1 to read just that bit. Set: OR with a mask that is 1 only at position i. Clear: AND with the complement of that mask (all 1s except position i). Toggle: XOR with the mask — XOR with 1 flips a bit, XOR with 0 leaves it alone.

These show up verbatim in Unix permission bits, feature-flag systems, bloom filters, and anywhere you pack multiple boolean flags into one integer to save space and cache misses.

Why XOR is magic

XOR gets its own section because it has properties the others don't:

• a ^ a = 0 — self-annihilation
• a ^ 0 = a — identity
• Commutative: a ^ b = b ^ a
• Associative: (a ^ b) ^ c = a ^ (b ^ c)

Put those together and you get: if you XOR a list of numbers where everything appears an even number of times, the result is 0. Because order doesn't matter (commutative + associative), you can mentally reorder all the pairs next to each other — each pair cancels — and whatever's left over is the answer.

flowchart LR
    A["a ^ b ^ a ^ c ^ b"] --> B["(a^a) ^ (b^b) ^ c"]
    B --> C["0 ^ 0 ^ c"]
    C --> D["c"]
    style D fill:#00ff9d,color:#0a0a0f
    style A fill:#1a1a2e,color:#e2e8f0

This isn't just a cute trick. It's genuinely the right tool for a class of problems, and recognizing when pairs cancel is the pattern.

Problem 1 — Single Number (LeetCode 136)

Every element in the array appears exactly twice except one. Find that element. O(n) time, O(1) space.

def single_number(nums: list[int]) -> int:
    result = 0
    for n in nums:
        result ^= n   # pairs cancel, lone element survives
    return result

# single_number([4, 1, 2, 1, 2]) → 4
# single_number([2, 2, 1])       → 1

One loop, one variable, no data structures. The hash set solution works too, but it uses O(n) memory — and in an interview, this one signals you know your bit manipulation cold.

n & (n-1): the lowest-set-bit eraser

This is the second trick worth memorizing. Let's see why it works.

When you compute n - 1, the lowest 1-bit in n flips to 0, and all the 0-bits below it flip to 1. When you AND that with n, the bits above the lowest set bit are unchanged (both n and n-1 agree there), and the lowest set bit plus everything below it all zero out (because n-1 has 0 where n had the set bit, and n has 0s where n-1 now has 1s).

n     = 10110100
n - 1 = 10110011
n & (n-1) = 10110000   ← lowest set bit cleared

flowchart TD
    N["n = 10110100"]
    N1["n-1 = 10110011"]
    R["n & (n-1) = 10110000"]
    N --> AND["&"]
    N1 --> AND
    AND --> R
    style N fill:#7c5cff,color:#fff
    style N1 fill:#22d3ee,color:#0a0a0f
    style R fill:#00ff9d,color:#0a0a0f

Problem 2 — Number of 1 Bits (Hamming weight, LeetCode 191)

Count the number of set bits in an unsigned integer.

The naive approach: loop through all 32 bits with a check. Fine. The bit-manipulation approach: repeatedly strip the lowest set bit with n & (n-1) and count how many times you do it before n hits zero. This runs in O(number of set bits), not O(bit width) — for sparse numbers, it's dramatically faster.

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

# hamming_weight(0b10110100) → 4  (four 1-bits)
# hamming_weight(0b11111111) → 8

Four lines. And the loop body is a single AND — the CPU eats this for breakfast.

Power of two check falls out of the same trick. A power of two has exactly one set bit. After one n & (n-1), it should be zero.

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

# is_power_of_two(16)  → True  (0b10000)
# is_power_of_two(6)   → False (0b110, two set bits)

That n > 0 check is load-bearing. 0 & -1 = 0 would incorrectly say 0 is a power of two without it.

Bitmasks for subsets

Here's the pattern that shows up most in harder problems: represent a subset of n elements as a bitmask, where bit i being 1 means "element i is in the subset."

A set of n elements has exactly 2^n subsets. Loop mask from 0 to (1 << n) - 1 and you've visited all of them. Check whether element i is in the current subset with (mask >> i) & 1.

flowchart TD
    S["Set: [a, b, c]  (n=3)"]
    M0["mask=000 → {}"]
    M1["mask=001 → {a}"]
    M2["mask=010 → {b}"]
    M3["mask=011 → {a,b}"]
    M4["mask=100 → {c}"]
    M5["mask=101 → {a,c}"]
    M6["mask=110 → {b,c}"]
    M7["mask=111 → {a,b,c}"]
    S --> M0 & M1 & M2 & M3 & M4 & M5 & M6 & M7
    style S fill:#7c5cff,color:#fff
    style M3 fill:#22d3ee,color:#0a0a0f
    style M7 fill:#00ff9d,color:#0a0a0f

Problem 3 — Subsets (LeetCode 78)

Given an array of distinct integers, return all subsets.

def subsets(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    result = []
    for mask in range(1 << n):          # 0 to 2^n - 1
        subset = []
        for i in range(n):
            if (mask >> i) & 1:         # bit i is set → include nums[i]
                subset.append(nums[i])
        result.append(subset)
    return result

# subsets([1, 2, 3]) →
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Time: O(n · 2ⁿ) — you're building 2ⁿ subsets, each requiring O(n) work to construct. This is the same complexity as the recursive backtracking version from subsets and permutations, but iterative, with no recursion stack overhead.

The constraint is obvious: this only works for small n. At n = 20 you have a million subsets; at n = 30 you're at a billion. If n is 30 or more, you need a smarter algorithm. But problems that say "n ≤ 20" or "n ≤ 25" are almost always inviting this pattern.

All four together: complexity

Operation	Time	Space	Note
Single bitwise op (AND/OR/XOR/shift)	O(1)	O(1)	CPU does it in one instruction
Check/set/clear/toggle bit i	O(1)	O(1)
Count set bits (n & (n-1) loop)	O(k)	O(1)	k = number of set bits
Count set bits (naive shift loop)	O(w)	O(1)	w = bit width (32 or 64)
Enumerate all subsets of n elements	O(n · 2ⁿ)	O(2ⁿ)	for storing results; O(1) extra if streaming
Single-number XOR	O(n)	O(1)	one pass, no allocation

The space column is what makes bit manipulation worth learning. The hash set approach to single-number is O(n) space. The XOR approach is O(1). That's not a minor improvement — it's the difference between a solution that might fail on a huge input and one that doesn't.

For a deeper treatment of when O(1) space matters at scale, the Big-O Notation crash course covers the space complexity analysis in detail.

The pitfalls people actually hit

Off-by-one on the shift. Bits are 0-indexed from the right. Bit 0 is the least significant. 1 << 0 = 1, 1 << 1 = 2, 1 << 3 = 8. Getting this wrong is embarrassing and common. When in doubt, print it and verify.

Signed integer overflow with left shifts. In Python you're fine — integers are arbitrary precision. In C, Java, or Go, shifting a 1-bit into the sign bit causes undefined behavior or unexpected negation. Use 1L << i (long) in Java if i can be ≥ 31.

~n in Python is not what you expect. Python integers are arbitrary precision and two's complement, so ~5 = -6, not a 26-bit number. This matters when you're trying to clear a bit with n & ~(1 << i) — it works, but if you're debugging and printing ~mask, the number will be negative and look wrong. It's correct, just surprising.

Forgetting the n > 0 guard on power-of-two. 0 & (0 - 1) in Python is 0 & -1 = 0, which is falsy, so actually this one is fine in Python. In C/Go with unsigned types, 0 - 1 wraps to MAX_UINT. Always add the guard.

Using bits when clarity matters more. is_power_of_two is a famous interview question. In production code, n > 0 and (n & (n-1)) == 0 is clever but opaque to someone reading it cold. math.log2(n) % 1 == 0 is slower and has float issues, but clearer. Be the person who leaves a comment. Bit tricks without a comment are a gift to your future self's debugging session.

Forgetting that XOR is its own inverse only for equality. a ^ b ^ a = b works because a ^ a = 0. But a ^ b ^ a ^ b = 0 — if a appears twice AND b appears twice, everything cancels. XOR finds the element that appears an odd number of times. If multiple elements appear an odd number of times, you need a more complex approach (usually XOR + bit partitioning — the "Single Number III" variant).

When NOT to reach for bit manipulation

Bit tricks are fast. They're not always appropriate.

When n is large and you need all subsets. If n > 25 or so, the 2ⁿ growth makes bitmask enumeration impractical. You need dynamic programming or a smarter combinatorial algorithm.

When you need set membership efficiently on arbitrary-sized sets. A bitmask works beautifully when your universe is ≤ 64 elements (fits in a 64-bit integer). For larger universes, you want a hash set or a bloom filter if you can tolerate false positives.

When the problem isn't actually about bits. Reach for the readable solution first. A sliding window, a prefix sum, or a two-pointer pass from two pointers may be clearer and equally fast. Bit manipulation is a specialist's tool, not a hammer for every nail.

When you're in a language without fixed-width integers and it matters. Python's arbitrary-precision integers make some tricks (like the canonical "invert all bits" approach to counting trailing zeros) behave differently than in C. Know your runtime.

Problem shape	Better tool
Element appears odd times	XOR — this article
Subset enumeration (small n ≤ 20)	Bitmask — this article
Subset enumeration (large n)	Backtracking or DP
Large set membership with no false positives	Hash set
Large set membership with occasional false positive OK	Bloom filter
Sorting or ranking	Sorting basics, not bits

Harder: subsets with a target sum

Given an array of n integers (n ≤ 20), find all subsets that sum to a target. Classic bitmask problem.

def subsets_with_target(nums: list[int], target: int) -> list[list[int]]:
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if (mask >> i) & 1]
        if sum(subset) == target:
            result.append(subset)
    return result

# subsets_with_target([3, 1, 4, 1, 5], 6)
# → [[3, 1, 1, 1], [1, 5], [1, 5], [3, 1, 1, 1]]  (not deduped, for clarity)

O(n · 2ⁿ) — checking every subset. For n = 20, that's 20 million operations, well under a second. The insight is just reading the constraints: when a problem caps n at 20–25, the intended solution is almost always bitmask enumeration. The extended version of this — bitmask dynamic programming, where the DP state is dp[mask] encoding which elements have been used — shows up in TSP variants and task-assignment problems. See dynamic programming for the full treatment.

The one thing to take away

Bit manipulation is a vocabulary, not a mystical art. Learn ten things:

1. AND/OR/XOR/NOT and what each does to individual bits.
2. Left shift = multiply by 2; right shift = divide by 2.
3. 1 << i makes a mask with only bit i set.
4. Check/set/clear/toggle are four patterns built from those two facts.
5. XOR: a ^ a = 0, a ^ 0 = a — pairs cancel, odd one survives.
6. n & (n-1) clears the lowest set bit.
7. Power of two iff n > 0 and (n & (n-1)) == 0.
8. Subsets of n elements: loop mask from 0 to (1 << n) - 1.
9. (mask >> i) & 1 tells you if element i is in subset mask.
10. This only scales to n ≈ 20–25; beyond that, reach for a real algorithm.

Know those cold, and when a problem hands you one of the canonical shapes — single odd-occurrence element, count set bits, enumerate small subsets, check power of two — you'll write the solution in fifteen seconds instead of spinning on it for five minutes.