Bit Manipulation

Core Concepts

Bit — a single binary digit, 0 or 1; the fundamental unit of storage in a computer.

Bitwise AND (&) — produces 1 only where both operands have 1; used to mask, check, and clear bits. a & b.

Bitwise OR (|) — produces 1 where at least one operand has 1; used to set bits. a | b.

Bitwise XOR (^) — produces 1 where operands differ; self-inverse (a ^ a = 0, a ^ 0 = a); used to toggle, find unique elements, and cancel duplicates.

Bitwise NOT (~) — flips all bits; in two's complement, ~n = -(n+1).

Left shift (<<) — shifts bits left by k positions; equivalent to multiplying by 2^k. n << k.

Right shift (>>) — shifts bits right by k positions; in Python this is always arithmetic (sign-extending); equivalent to floor-dividing by 2^k. n >> k.

Two's complement — standard signed integer encoding: the most significant bit (MSB) is the sign bit; negation via ~n + 1; range for 32-bit: −2^31 to 2^31 − 1.

Least significant bit (LSB) — the rightmost bit; extracted with n & 1 or n & -n.

Most significant bit (MSB) — the leftmost set bit; its position is floor(log2(n)).

Popcount (population count) — the number of set bits in an integer. Also called Hamming weight.

Hamming distance — number of bit positions where two integers differ; equals popcount(a ^ b).

Bitmask — an integer used to select or manipulate a specific subset of bits. A mask for bit k: 1 << k.

Bit manipulation identity cheat-sheet:

---

Types / Variants

See dynamic-programming.md for general DP coverage; bitmask DP fits naturally there too.

---

Key Algorithms

Check / Set / Clear / Toggle a Bit

Check bit k: (n >> k) & 1. Set: n | (1 << k). Clear: n & ~(1 << k). Toggle: n ^ (1 << k). All O(1).

Count Set Bits (Brian Kernighan)

Repeatedly clear the lowest set bit with n &= n - 1 until n = 0; count iterations. O(popcount) — faster than O(32) when set bits are sparse.

Isolate Lowest Set Bit

n & -n — exploits two's complement: -n = ~n + 1; the only bit set in both n and -n at the same position is the lowest set bit. O(1).

Enumerate All Subsets of a Bitmask

sub = mask
while sub:
    # process sub
    sub = (sub - 1) & mask

Iterates over all non-empty subsets; the last & mask keeps the result within the original mask. Total iterations across all masks of n bits: 3^n (sum of 2^popcount over all n-bit masks).

Enumerate All Subsets of Size k (Gosper's Hack)

c = n & -n; r = n + c; nxt = (((r ^ n) >> 2) // c) | r

Produces the next integer with the same popcount; iterate until overflow. O(1) per step. Use when you must visit all C(n, k) subsets exactly.

XOR Linear Basis (Gaussian Elimination on Bits)

Maintains a set of linearly independent integers over GF(2). Insert each number by trying to reduce it against existing basis elements from the highest bit. After building the basis, the maximum XOR of any subset equals the maximum reachable value by greedily choosing basis elements. O(n · log(max_val)).

basis = []
for x in nums:
    for b in basis:
        x = min(x, x ^ b)
    if x:
        basis.append(x)

Solves: maximum XOR subset, count distinct XOR values reachable from a set.

Binary Trie for Maximum XOR Pair

Insert all numbers as 32-bit paths in a trie (MSB first). For each number, greedily follow the opposite bit at each level to maximise XOR. O(n · 32). Handles online queries and "maximum XOR with any prefix element" problems.

Prefix XOR (Range XOR Query)

pre[i] = a[0] ^ a[1] ^ ... ^ a[i-1]. Range XOR [l, r] = pre[r+1] ^ pre[l]. O(n) build, O(1) query. Use with a hashmap to find subarrays whose XOR equals a target k: count pre[j] ^ k in prefix XOR seen so far.

Fast Power of Two Checks

n > 0 and (n & (n-1)) == 0 — true iff n is a power of 2. O(1). Consequence: n & (n-1) strips exactly the lowest set bit, so iterating it counts set bits (Brian Kernighan) and can test power-of-2.

Integer Reversal / Bit Reversal

To reverse 32 bits: swap blocks of 16, then 8, then 4, then 2, then 1, using masks and shifts. O(log 32) = O(1). The mask for even bits: 0x55555555; for odd bits: 0xAAAAAAAA.

Gray Code Generation

n-th Gray code: n ^ (n >> 1). Consecutive codes differ by exactly 1 bit. Used in interval/subset enumeration where single-bit transitions matter. O(1) per element.

---

Advanced Techniques

Bitmask DP

Solves: combinatorial assignment/matching problems on n ≤ 20 items (TSP, minimum cost assignment, set cover, counting Hamiltonian paths).

Mechanism: State dp[mask] represents optimal result over the subset of items encoded in mask. Transitions extend the subset by one item. Enumerate subsets via the "next subset" trick.

When to prefer over alternatives: Only when n ≤ 20 (state space is 2^n). For n > 20, use meet-in-the-middle or approximation. Never reach for bitmask DP when a greedy or network-flow solution exists; bitmask DP is exponential.

Complexity: O(2^n · n) time, O(2^n) space.

XOR Linear Basis (Advanced)

Solves: Maximum XOR subset, count of distinct XOR values, k-th smallest XOR value, XOR span of a set.

Mechanism: Gaussian elimination over GF(2); maintains at most 30/64 basis vectors. Any reachable XOR is a linear combination of basis elements.

When to prefer: When the problem involves XOR over arbitrary subsets (not just pairs). For pairs only, binary trie is simpler.

Complexity: O(n · log(max_val)) build; O(log(max_val)) per query.

Meet in the Middle (Bitwise)

Solves: Subset XOR/sum target with n up to 40; exhaustive enumeration too slow at O(2^40).

Mechanism: Split the array in half, enumerate all 2^(n/2) XOR values for each half, then for each value in the first half use binary search or a hashset on the second half.

When to prefer over bitmask DP: n is 30–40 (too large for 2^n but feasible for 2·2^(n/2)).

Complexity: O(2^(n/2) · n/2).

Bit Tricks for O(1) Aggregates (SWAR — SIMD Within A Register)

Solves: Popcount, parity, and parallel prefix operations without loops.

Mechanism: Accumulate partial sums across bit-fields packed into a single integer using carefully chosen masks. The popcount sequence: split into 2-bit groups, then 4-bit, then bytes, then add bytes.

When to prefer: When bin(n).count('1') or int.bit_count() is unavailable or you need to understand the underlying technique for interview purposes. In practice, use bin(n).count('1') in Python.

Complexity: O(log W) operations where W = word size.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Signed integer overflow in non-Python languages: shifting 1 << 31 in a 32-bit int overflows; use 1 << 31 as unsigned or cast to 64-bit. Python integers are arbitrary precision, so this doesn't apply, but be aware when translating to Java/C++.

• ~n is not the same as XOR with all-ones mask: ~5 in Python is -6, not 26, because Python integers have infinite precision. To get a 32-bit NOT, use n ^ 0xFFFFFFFF.

• Right shift semantics: Python >> is arithmetic (preserves sign). In Java/C++, >> is arithmetic and >>> is logical (zero-fills). Know which you need when handling negative numbers.

• XOR swap breaks on aliased inputs: a ^= b; b ^= a; a ^= b gives 0 if a and b are the same variable or same memory location.

• Off-by-one in bit indexing: bit k is 1 << k, not 1 << (k+1). Confusing 0-indexed vs. 1-indexed bit positions corrupts masks.

• Forgetting the zero subset in subset enumeration: the sub = (sub-1) & mask loop stops before processing sub = 0. If the empty subset is valid, handle it separately after the loop.

• Bitmask DP space: 2^20 states = ~1M entries, which is fine. 2^25 = 32M entries may exceed memory. Check constraints before committing to bitmask DP.

• Linear basis insertion order matters for k-th XOR: reducing to reduced row echelon form (each basis element has a unique highest bit that no other basis element has) is required for k-th smallest XOR queries; a raw basis does not suffice.

• AND of range shrinks quickly to zero: [l, r] AND converges to the common bit prefix; for large ranges this is often 0. Don't expect a non-trivial answer.

• Parity vs. popcount confusion: parity is popcount mod 2, extractable as the XOR of all bits. Popcount is the full count. They are different operations.

---

Implementation Notes

• Python int.bit_count() (3.10+) returns popcount directly; bin(n).count('1') works on all versions.
• Python int.bit_length() returns the position of the MSB + 1 (e.g., (6).bit_length() == 3).
• For 32-bit simulation in Python, mask results with & 0xFFFFFFFF and handle sign with if result >= 2**31: result -= 2**32.
• n & -n uses Python's arbitrary-precision two's complement correctly — no special casing needed.
• Bitmask DP arrays: use [0] * (1 << n) for 0-indexed masks 0 to 2^n − 1; ensure n is small enough before allocation.
• When iterating all subsets of all masks in O(3^n), the outer loop is for mask in range(1 << n) and the inner is the sub = (sub-1) & mask pattern.
• collections.Counter + XOR cancellation can be replaced by a single pass XOR for the "find single non-duplicate" pattern — don't over-engineer it.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Bit tricks / single-pass XOR

• Single Number (136) — XOR all elements
• Single Number II (137) — count bits mod 3
• Single Number III (260) — two-group XOR split
• Missing Number (268) — XOR with indices
• Find the Difference (389)

Popcount and bit counting

• Number of 1 Bits (191) — Brian Kernighan or built-in
• Counting Bits (338) — DP: dp[i] = dp[i >> 1] + (i & 1)
• Hamming Distance (461)
• Total Hamming Distance (477) — count contribution of each bit position

Power / divisibility checks

• Power of Two (231)
• Power of Four (342)
• Reverse Bits (190)
• Reverse Integer (7) — adjacent to bit manipulation in interviews

Range and subarray XOR

• XOR Queries of a Region (1310) — prefix XOR
• Subarray XOR Less Than k — prefix XOR + trie
• Count Triplets That Can Form Two Arrays of Equal XOR (1442)

Maximum XOR

• Maximum XOR of Two Numbers in an Array (421) — binary trie
• Maximum XOR With an Element From Array (1707) — offline + trie
• Maximum AND Sum of Array (2172) — bitmask DP

Bitmask DP

• Partition to K Equal Sum Subsets (698)
• Minimum Cost to Connect Two Groups (1595)
• Shortest Path Visiting All Nodes (847)
• Number of Ways to Wear Different Hats (1434)
• Find the Shortest Superstring (943) — TSP-style

Subset enumeration

• Subsets (78) — generate via bitmask
• Subsets II (90) — with duplicates

Additional LeetCode Coverage

• Bitwise AND of Numbers Range (LC 201)
• Sum of Two Integers (LC 371)
• Minimum Flips to Make a OR b Equal to c (LC 1318)
• Number of Steps to Reduce a Number to Zero (LC 1342)
• Divide Two Integers (LC 29)

Clarification Questions to Ask

• Are integers 32-bit signed or 64-bit? Python is arbitrary precision, but the problem may define a fixed width.
• Is the input guaranteed non-negative? Negative numbers with right-shift behave differently in other languages.
• For "find maximum XOR", are we XORing two elements, any subset, or a prefix with any element?
• For bitmask DP problems: confirm n ≤ 20 (otherwise the approach is infeasible).
• For range AND/OR: are l and r inclusive or exclusive?

Common Interview Mistakes

• Using ~n expecting a bit-flip within a fixed word size — in Python this gives a negative number; mask with 0xFFFFFFFF instead.
• Forgetting to handle the zero/empty subset separately in the sub = (sub-1) & mask loop.
• Applying bitmask DP to n = 30+ without checking memory — 2^30 entries exceed typical limits.
• Using XOR swap on aliased variables (results in 0).
• Confusing n & (n-1) (clears lowest set bit) with n | (n-1) (sets bits below lowest set bit) — the off-by-one here causes wrong answers silently.
• Building a binary trie but querying from LSB instead of MSB — the greedy maximisation only works MSB-first.
• Missing that XOR cancellation requires pairs: if an element appears 3 times, XOR gives 1 occurrence back, not 0.

Typical Follow-Up Escalations

• "Now find the two numbers appearing once (others appear twice)" → split by any set bit of the combined XOR of the two missing values.
• "Now support range XOR queries on a mutable array" → BIT/Fenwick tree with XOR instead of sum, or segment tree.
• "Now find the maximum XOR of any subset, not just a pair" → XOR linear basis (Gaussian elimination over GF(2)).
• "Now do it for k = 20 elements, find the minimum cost assignment" → bitmask DP with state = set of assigned items.
• "What if the numbers are up to 10^18?" → extend binary trie to 60 bits or use a 64-bit linear basis; no structural change.