Bit Manipulation

TL;DR

Bit manipulation is two ideas glued together. The first is XOR cancelation: a ^ a = 0 and a ^ 0 = a, and XOR is associative and commutative, so any collection of values XOR’d together collapses to whatever appears an odd number of times. That alone solves a whole class of “find the unique element” problems in O(n) time and O(1) space.

The second is bitmasks: when you have a small set (≤ ~20 elements), pack membership into the bits of an integer. Now “is element i in the set?” is mask & (1 << i), “add i” is mask | (1 << i), and “iterate every subset” is for mask in range(1 << n). Set operations become single CPU instructions.

A handful of bit identities show up everywhere: popcount (count set bits), low-bit isolation x & -x (the lowest set bit, value and position), and Brian Kernighan’s x & (x - 1) (clear the lowest set bit). Stack these on top of bitmasks and you get bitmask DP — dp[mask][i] indexed by “subset visited so far” — the standard tool for held-karp TSP and assignment problems on small n.

If a problem looks combinatorial on a small set, or screams “exactly one odd occurrence,” reach for bits before reaching for hash maps.

When to reach for it

Signals that bit manipulation is the right move:

• The state space is a small set of ≤ ~20 elements and you need to enumerate or DP over its subsets. 2^20 ≈ 10^6 masks is fine; 2^25 is the practical ceiling.
• The problem says “find the element that appears once / odd times” while every other element appears in pairs (or in groups whose count cancels under XOR).
• You need parity (even/odd count of something) or popcount of an integer.
• You’re packing flags — permission bits, feature toggles, capability sets — and want union/intersection/difference in O(1).
• The constraint is “O(1) extra space” and the natural solution wants a hash set.

Signals that it’s not bits:

• Float math, fractional weights, or anything where bitwise operations don’t have arithmetic meaning.
• Large state spaces — once n > ~25, 2^n masks blow past memory and time budgets; you want a different DP or a heuristic.
• Order-sensitive problems where you need a sequence, not a set. A mask loses ordering by construction.

Flavor 1 — XOR tricks

The canonical XOR problem: every element appears twice except one. Find the single element.

def single_number(nums: list[int]) -> int:
    out = 0
    for x in nums:
        out ^= x
    return out

Pairs cancel because a ^ a = 0, the survivor is the unpaired element, and order doesn’t matter because XOR commutes. O(n) time, O(1) space.

Worked example. nums = [4, 1, 2, 1, 2]. Run XOR left to right:

The 1s and 2s pair off and zero out; 4 survives.

Missing number (LC 268). Given [0..n] with one missing, XOR all values and all indices 0..n together:

def missing_number(nums: list[int]) -> int:
    out = len(nums)             # seed with n itself
    for i, x in enumerate(nums):
        out ^= i ^ x
    return out

Every present value cancels with its index; the missing value’s index has no partner and survives.

Pair detection. Two numbers appear once, everyone else twice (LC 260)? XOR everything to get a ^ b. Pick any set bit of that result — (a^b) & -(a^b) — that bit splits the input into two groups, each containing exactly one of the unique elements. XOR each group separately.

Flavor 2 — bitmask membership and counting bits

Three identities you’ll use forever:

• x & (1 << i) — test whether bit i is set.
• x | (1 << i) — set bit i.
• x & ~(1 << i) — clear bit i.
• x ^ (1 << i) — toggle bit i.

For counting set bits, Brian Kernighan’s trick beats the naive loop. The expression x & (x - 1) clears the lowest set bit of x, because subtracting 1 flips the lowest set bit and every bit below it; AND-ing with the original keeps only the bits above:

def popcount(x: int) -> int:
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

The loop runs once per set bit, not once per bit position. For sparse integers it’s much faster than scanning all 32 or 64 positions.

Worked example. x = 0b10110100 (decimal 180). Successive x & (x-1):

Four set bits, four iterations. Loop terminates the moment x hits zero.

Low-bit isolation. x & -x returns just the lowest set bit (as a power of two). On x = 0b10110100, -x in two’s complement is ...01001100, and x & -x = 0b00000100, the value-4 bit. This is what Fenwick (BIT) trees use to walk index ranges.

Flavor 3 — subset enumeration via bitmask

To enumerate every subset of a set of size n, iterate masks 0 through 2^n - 1 and read each bit:

def all_subsets(items: list) -> list[list]:
    n = len(items)
    out = []
    for mask in range(1 << n):
        subset = [items[i] for i in range(n) if mask & (1 << i)]
        out.append(subset)
    return out

For n = 4 and items = [a, b, c, d], masks 0..15 map cleanly:

Bit i of mask decides whether items[i] is in the subset. The order is arbitrary but deterministic — useful for memoization keys.

Flavor 4 — bitmask DP (brief)

When the state of a DP includes “which elements have I used so far” and the universe is small, encode that set as a mask. Held-Karp TSP is the canonical example: dp[mask][i] = minimum cost to have visited the cities in mask, currently sitting at city i.

# dp[mask][i]: min cost over a path that visits exactly the cities in `mask`
# and ends at city i. Transition: for j not in mask, try extending to j.
# Final answer: min over i of dp[(1<<n)-1][i] + dist[i][0].

Complexity is O(2^n · n^2) — fine for n ≤ 20, hopeless past 25. The takeaway: when “subset visited” needs to live in your DP key, a mask makes it O(1) to hash and O(1) to extend.

Why it works — the invariant

XOR forms an abelian group on bit-vectors: associative, commutative, every element is its own inverse. That’s exactly the algebraic structure that makes “pair off duplicates” work — order doesn’t matter, equal pairs cancel, and what’s left is the symmetric difference of the input multiset against itself. Every XOR trick is a different presentation of the same group law.

Bitmasks work because a CPU word is a small set. Union is |, intersection is &, difference is & ~, symmetric difference is ^, cardinality is popcount. Each is one instruction. You’re not simulating sets; you’re using the hardware’s native representation of them.

Complexity

• XOR scans — O(n) time, O(1) space. One pass, one accumulator.
• Popcount via Kernighan — O(k) where k is the number of set bits, bounded by the word size.
• Subset enumeration — O(2^n · n): 2^n masks, O(n) work to materialize each subset. If you only need the mask itself (not the list), it’s O(2^n).
• Bitmask DP — typically O(2^n · n) or O(2^n · n^2) depending on transitions. Memory is O(2^n · n) for the table.

Common pitfalls

• Python ints are arbitrary precision. No overflow safety net like in C. That sounds great until you accidentally produce a multi-thousand-bit integer in a tight loop and wonder why it’s slow. Mask down explicitly (x & 0xFFFFFFFF) when you’re emulating fixed-width arithmetic — LC 371 (Sum of Two Integers) is the classic trap.
• Signed-shift gotchas in non-Python languages. In C/C++, right-shifting a negative signed int is implementation-defined; in Java, >> is arithmetic and >>> is logical. If you’re porting Python solutions, pick the right operator.
• Off-by-one when shifting. 1 << n is 2^n, not 2^n - 1. To build “all bits set for an n-element universe,” it’s (1 << n) - 1. To loop every subset, it’s range(1 << n) (i.e. 0 through 2^n - 1 inclusive). Mixing 1 << n and 1 << (n - 1) is the most common source of silent bugs.
• x & -x only works under two’s complement. Python integers behave as if they’re in two’s complement for bitwise ops, which is why this works there. In a language with sign-magnitude or unsigned-only types, the trick needs adjustment.
• Forgetting that popcount and shifts aren’t free above word size. Once your masks exceed 64 bits, & and | are still cheap-per-word but no longer single-instruction. Bitmask DP at n = 30 is not 2x slower than n = 29; it’s 2x slower and chewing through cache.

Where you see this in production

• CPU feature flag detection (CPUID). x86’s CPUID instruction returns feature support as bits packed into EAX/EBX/ECX/EDX. Detecting AVX-512 is (ecx >> 27) & 1. Compilers, kernels, and ML kernels (oneDNN, MKL) all read these bitfields at startup to dispatch to the right code path.
• Linux capability sets. CAP_NET_ADMIN, CAP_SYS_PTRACE, and the rest are bit positions in a 64-bit cap_t. Granting a capability is caps |= 1ULL << CAP_X; checking is caps & (1ULL << CAP_X). POSIX file mode bits (S_IRUSR, S_IWUSR, …) work the same way.
• Roaring Bitmaps in OLAP engines. Elasticsearch (postings), Apache Druid (segment filters), and ClickHouse use Roaring Bitmaps to store large sets of document IDs compactly and intersect them with bitwise AND. Filtered queries reduce to set algebra over compressed bitmaps.
• TCP header flag fields. SYN, ACK, FIN, RST, PSH, URG live in a single byte of the TCP header. Every packet your machine sends or receives is matched against those bits with masks — (flags & TH_SYN) && !(flags & TH_ACK) is the check for “this is a connection request.”

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.