Bit Manipulation - Dev Weekends

What is Bit Manipulation?

Bit Manipulation uses bitwise operators to solve problems at the binary level. It enables O(1) operations for many tasks and reduces space complexity. Think of every integer as a row of light switches — each switch is either ON (1) or OFF (0). Bit manipulation is the art of flipping, reading, and combining those switches directly, without converting to decimal. This is the language your CPU already speaks, which is why bitwise operations are as fast as operations can get. Why does this matter for interviews? Bit manipulation lets you solve certain problems in O(1) space and O(n) time that would otherwise require hash sets or sorting. The XOR trick for “find the unique element” is a classic example: no extra memory, one pass, elegant. Interviewers love it because it tests whether you understand what is happening beneath the abstraction. Key mental model: Every integer is a fixed-width binary string (32 or 64 bits in most languages). Operations like AND, OR, and XOR operate on each bit position independently and in parallel — all 32 bits are processed in a single CPU instruction.

LeetCode Pattern Recognition Cheatsheet — when to reach for bit manipulation:

“Find the single number” — every element appears twice except one (or thrice except one). XOR cancels pairs in O(1) space. (LC 136, 137, 260)
“Count set bits / popcount” — bit hacks like Brian Kernighan run in O(popcount) instead of O(32). (LC 191, 338)
“Power of two / power of four” — n & (n - 1) == 0 short-circuits the loop. (LC 231, 342)
“Generate all subsets” — iterate i from 0 to 2^n - 1. Each integer is a subset bitmask. (LC 78, 90)
“Bitmask DP” — state space tracks which elements/cities/tasks are visited. Use when n is at most around 20-24. (LC 691, 1125, TSP)
“Swap without temp / multiply or divide by 2” — shift operations are nearly free at the hardware level.
“Find the missing number” — XOR with the full range cancels matched pairs. (LC 268)
“Maximum XOR pair” — bit-trie greedy approach, scanning from MSB. (LC 421)
“Hamming distance / total Hamming distance” — XOR plus popcount. (LC 461, 477)

If the problem mentions a small set (n at most around 20), independent bit positions, parity, or “every element appears k times except one,” XOR or bitmask is almost always the intended approach.

Essential Operations

# Basic operators
a & b   # AND: 1 only if both bits are 1
a | b   # OR: 1 if either bit is 1
a ^ b   # XOR: 1 if bits are different
~a      # NOT: flip all bits
a << n  # Left shift: multiply by 2^n
a >> n  # Right shift: divide by 2^n

Common Tricks

Each trick exploits a specific property of binary representation. Understanding why each works is more important than memorizing the formulas.

# Check if nth bit is set (0-indexed from the right)
# Shift n right so the target bit lands at position 0, then mask with 1
(num >> n) & 1

# Set nth bit to 1
# Create a mask with only bit n set, then OR it in
num | (1 << n)

# Clear nth bit (set to 0)
# Create a mask with every bit set EXCEPT bit n, then AND it
num & ~(1 << n)

# Toggle nth bit (flip 0->1 or 1->0)
# XOR with a mask that has only bit n set
num ^ (1 << n)

# Check if power of 2
# Powers of 2 have exactly one bit set: 8 = 1000, 8-1 = 0111, AND = 0000
n > 0 and (n & (n - 1)) == 0

# Get lowest set bit (isolate it)
# -n is the two's complement: flips all bits and adds 1, so only the
# lowest set bit survives the AND
n & (-n)

# Clear lowest set bit (turn it off)
# n-1 flips the lowest set bit and all bits below it; AND removes it
n & (n - 1)

# Count set bits (Brian Kernighan's algorithm)
# Each iteration removes exactly one set bit, so we loop popcount times
count = 0
while n:
    n &= n - 1    # Remove lowest set bit
    count += 1

Pattern Variations

1. Single Number

The poster child of bit manipulation. XOR has three properties that make this work:

Self-inverse: a ^ a = 0 (any number XOR itself vanishes)
Identity: a ^ 0 = a (XOR with zero changes nothing)
Commutative and associative: order does not matter

So if you XOR every element, all pairs cancel out and only the unique element survives. Walked example: nums = [4, 1, 2, 1, 2] — XOR all: 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4. Time: O(n). Space: O(1). No hash set needed.

def single_number(nums):
    """Find element that appears once (others twice)"""
    result = 0
    for num in nums:
        result ^= num     # Pairs cancel: a ^ a = 0; unique value remains
    return result

# XOR properties: a ^ a = 0, a ^ 0 = a, commutative + associative

2. Counting Bits

A beautiful DP-meets-bit-manipulation problem. The recurrence result[i] = result[i >> 1] + (i & 1) says: “the number of set bits in i equals the number of set bits in i with its last bit removed (i >> 1), plus whatever that last bit was (i & 1).” Walked example: i=5 (binary 101). i >> 1 = 2 (binary 10, has 1 set bit). i & 1 = 1. So result[5] = 1 + 1 = 2. Correct: 101 has two 1-bits. Time: O(n). Space: O(n).

def count_bits(n):
    """Count set bits for all numbers 0 to n"""
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 drops the last bit; i & 1 checks if the last bit is 1
        result[i] = result[i >> 1] + (i & 1)
    return result

3. Subsets Using Bitmask

An elegant alternative to backtracking for generating subsets. Each integer from 0 to 2^n - 1 is a bitmask where bit i means “include nums[i].” The bitmask 5 (binary 101) represents the subset containing nums[0] and nums[2]. This approach is often simpler to code and harder to get wrong than recursive backtracking, but it only works when n is small (n at most around 20, since 2^20 is about a million). Time: O(n * 2^n). Space: O(1) (excluding output).

def subsets(nums):
    """Generate all subsets using bitmask"""
    n = len(nums)
    result = []
    
    for mask in range(1 << n):     # Iterate over all 2^n bitmasks
        subset = []
        for i in range(n):
            if mask & (1 << i):    # If bit i is set, include nums[i]
                subset.append(nums[i])
        result.append(subset)
    
    return result

# Walkthrough with nums = [a, b, c]:
#   mask=0 (000) -> []
#   mask=1 (001) -> [a]
#   mask=2 (010) -> [b]
#   mask=3 (011) -> [a, b]
#   mask=4 (100) -> [c]
#   mask=5 (101) -> [a, c]
#   mask=6 (110) -> [b, c]
#   mask=7 (111) -> [a, b, c]

4. Missing Number

def missing_number(nums):
    """Find missing number in [0, n]"""
    n = len(nums)
    result = n  # Start with n (might be missing)
    
    for i, num in enumerate(nums):
        result ^= i ^ num
    
    return result

5. Reverse Bits

def reverse_bits(n):
    """Reverse bits of 32-bit unsigned integer"""
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

Classic Problems

1. Power of Two

Check: n greater than 0 and (n & (n-1)) equals 0Why: Power of 2 has exactly one bit set

2. Hamming Distance

Formula: count set bits in (x ^ y)Why: XOR gives 1 where bits differ

3. Add Without Plus

Pattern: sum = a ^ b, carry = (a & b) left-shifted by 1Why: XOR adds without carry, AND gives carry positions

4. Maximum XOR

Pattern: Build trie of binary representationsWhy: Greedily choose opposite bit for maximum XOR

Bit Manipulation in DP

def can_partition(nums):
    """Subset sum using bitset DP"""
    bits = 1  # bits represents reachable sums
    
    for num in nums:
        bits |= bits << num
    
    total = sum(nums)
    return total % 2 == 0 and (bits >> (total // 2)) & 1

Common Mistakes

Avoid These Pitfalls:

Signed vs unsigned confusion: Python integers have arbitrary precision, so 1 << 40 just works. But in Java/C++, 1 << 32 on an int is undefined behavior or wraps around. Use 1L << n in Java for shifts beyond 31.
Operator precedence gotchas: Bitwise operators have lower precedence than comparison operators in most languages. x & 1 == 0 is parsed as x & (1 == 0) which is x & 0, not (x & 1) == 0. Always use parentheses: (x & 1) == 0.
Off-by-one in shifts: 1 << n creates a mask for bit n (0-indexed). Shifting by the bit-width (e.g., 1 << 32 for a 32-bit int) is undefined in C/C++ and produces 0 in Java. Know your language’s rules.
Negative numbers and right shift: In Java/C++, the arithmetic right shift (>>) sign-extends (fills with the sign bit). Use >>> in Java for unsigned right shift. In C++, right-shifting a negative number is implementation-defined.
Forgetting to handle n = 0 in power-of-two check: 0 & (0 - 1) == 0 is true, but 0 is not a power of 2. Always include the n > 0 guard.

Quick Reference

Operation	Code	Description
Get bit	`(n >> i) & 1`	Get ith bit
Set bit	`n OR (1 left-shift i)`	Set ith bit to 1
Clear bit	`n & ~(1 left-shift i)`	Set ith bit to 0
Toggle bit	`n ^ (1 left-shift i)`	Flip ith bit
Lowest bit	`n & (-n)`	Isolate lowest set bit
Clear lowest	`n & (n-1)`	Remove lowest set bit

Operator and Trick Cheatsheet

A condensed reference you can re-derive in an interview. Memorize the why, not just the line.

Goal	One-liner	Why it works
AND	`a & b`	Both bits set
OR	`a \| b`	Either bit set
XOR	`a ^ b`	Bits differ
NOT	`~a`	Flip every bit (in fixed width)
Get bit i	`(n >> i) & 1`	Move bit i to position 0, mask
Set bit i	`n \| (1 << i)`	Mask in a 1 at position i
Clear bit i	`n & ~(1 << i)`	Mask out position i
Toggle bit i	`n ^ (1 << i)`	XOR flips that bit
Lowest set bit	`n & (-n)`	Two’s complement isolates it
Clear lowest set bit	`n & (n - 1)`	Brian Kernighan
Is power of 2?	`n > 0 && (n & (n - 1)) == 0`	Exactly one set bit
Flip all bits in fixed width	`n ^ -1` (or `n ^ ((1 << w) - 1)`)	XOR with all-ones mask
Multiply by 2	`n << 1`	Left shift
Divide by 2 (unsigned)	`n >> 1`	Logical right shift
Swap without temp	`a ^= b; b ^= a; a ^= b;`	XOR cancels pairs

Iterating Subsets of a Bitmask

A surgical trick that shows up in bitmask DP. Given a bitmask mask, enumerate every subset (including empty) in time proportional to the number of subsets, not the universe.

Python

sub = mask
while True:
    process(sub)              # do work for this subset
    if sub == 0:
        break
    sub = (sub - 1) & mask    # next subset, walking downward

Java

int sub = mask;
while (true) {
    process(sub);
    if (sub == 0) break;
    sub = (sub - 1) & mask;
}

C++

int sub = mask;
while (true) {
    process(sub);
    if (sub == 0) break;
    sub = (sub - 1) & mask;
}

Why it works: subtracting 1 from a non-zero bitmask flips the lowest set bit and turns on all bits below it. ANDing with mask strips the new lower bits that are not part of the original set. Each step lands on a strict subset of mask, eventually reaching 0. Total iterations: exactly 2^popcount(mask). Where it shows up: sum-over-subsets DP, partition problems (LC 1125 Smallest Sufficient Team), travelling-salesman-style bitmask DP, “split set into two non-empty groups” interval problems.

Worked LeetCode Problems

Six canonical bit problems mapped to the patterns above. Each one is a template you can copy-adapt in interviews.

LC 136 — Single Number (Easy)

Pattern: XOR cancellation. Every element appears twice except one.

Python

def singleNumber(nums):
    result = 0
    for x in nums:
        result ^= x   # pairs cancel, the unique survives
    return result

XOR is associative and commutative, so we can mentally regroup the input as (a ^ a) ^ (b ^ b) ^ ... ^ unique = unique. O(n) time, O(1) space.

LC 191 — Number of 1 Bits (Easy)

Pattern: Brian Kernighan’s algorithm.

Python

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

Runs in O(popcount) iterations, not O(32). For sparse integers this is significantly faster than the naive for i in range(32): count += (n >> i) & 1.

LC 338 — Counting Bits (Easy, DP + bit insight)

Pattern: DP recurrence using the lowest-bit trick.

Python

def countBits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)   # i has popcount(i//2) plus parity bit
        # alternative: dp[i] = dp[i & (i - 1)] + 1
    return dp

Two valid recurrences:

dp[i] = dp[i >> 1] + (i & 1) — chop off the lowest bit, look up half.
dp[i] = dp[i & (i - 1)] + 1 — clear the lowest set bit, add one.

Both are O(n) total. The second is more general and reusable.

LC 268 — Missing Number (Easy)

Pattern: XOR with the full range. Cancels every present number.

Python

def missingNumber(nums):
    result = len(nums)              # XOR includes n
    for i, x in enumerate(nums):
        result ^= i ^ x             # cancels matched pair (i, x_i)
    return result

Works because 0 ^ 1 ^ ... ^ n XOR’d against nums (which contains all but one of those values) leaves only the missing one. The len(nums) seed accounts for the upper bound n not being one of the loop indices.

LC 78 — Subsets (Medium, bitmask iteration)

Pattern: Each integer in [0, 2^n) is a subset bitmask.

Python

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

For each mask, bit i decides whether nums[i] is included. Generates all 2^n subsets in O(n * 2^n) total — same asymptotic cost as backtracking but with no recursion stack.

LC 421 — Maximum XOR of Two Numbers in an Array (Medium, trie + bit greedy)

Pattern: Build a binary trie of bits MSB-to-LSB. For each number, walk the trie greedily preferring the opposite bit to maximize XOR.

Python

def findMaximumXOR(nums):
    max_xor = 0
    mask = 0
    for i in range(31, -1, -1):
        mask |= (1 << i)                   # add the next high bit to consider
        prefixes = {x & mask for x in nums}
        candidate = max_xor | (1 << i)     # hope this bit can be set in the answer
        # if any pair of prefixes XORs to candidate, that bit is achievable
        if any((candidate ^ p) in prefixes for p in prefixes):
            max_xor = candidate
    return max_xor

The trie approach is cleaner conceptually (build trie, query each number, O(32n) per pass) but the prefix-set approach above is O(32n) and fits in fewer lines. Either is acceptable in an interview.

Pitfalls and traps to know cold:

Java int is 32-bit signed. 1 << 31 is Integer.MIN_VALUE. For 64-bit shifts, use 1L << n. Use >>> for logical (unsigned) right shift; >> sign-extends.
Negative numbers in two’s complement. ~n == -n - 1. To flip all bits in a fixed width w, XOR with (1 << w) - 1, not with ~0 (which is -1 in Java/C++ and arbitrary in Python).
Operator precedence is the silent killer. x & 1 == 0 is parsed as x & (1 == 0). Always parenthesize: (x & 1) == 0.
Bitmask DP has a hard ceiling. 2^n states explode. Stay under roughly n equals 20-24 unless you can prune the state space.
Power-of-two check needs the zero guard. n & (n - 1) == 0 is also true for n == 0. Add n > 0.
Python integers are unbounded. ~0 is -1, not a 32-bit complement. Mask with & 0xFFFFFFFF when you need fixed-width semantics (Reverse Bits, Add Without Plus).
Shift by the word width is undefined behavior in C/C++. 1 << 32 on a 32-bit int is UB. In Java the shift amount is taken modulo 32 for int (so 1 << 32 is 1, surprising the unwary).

The five lines you should be able to write under pressure:

n & (n - 1) — clear lowest set bit (popcount, power of 2)
n & (-n) — isolate lowest set bit
(mask >> i) & 1 — read bit i
mask | (1 << i) — set bit i
sub = (sub - 1) & mask — next subset of mask

Curated LeetCode List

A focused list grouped by sub-pattern. Solve in order; you will see the same five tricks reused.

LC #	Problem	Difficulty	Sub-pattern
136	Single Number	Easy	XOR cancellation
191	Number of 1 Bits	Easy	Brian Kernighan
231	Power of Two	Easy	`n & (n - 1) == 0`
268	Missing Number	Easy	XOR with range
338	Counting Bits	Easy	DP plus bit recurrence
78	Subsets	Medium	Bitmask enumeration
137	Single Number II	Medium	Bit-counting mod 3
260	Single Number III	Medium	XOR plus partitioning bit
371	Sum of Two Integers	Medium	XOR plus carry loop
421	Maximum XOR of Two Numbers	Medium	Trie or prefix greedy
477	Total Hamming Distance	Medium	Per-bit counting
1125	Smallest Sufficient Team	Hard	Bitmask DP

Practice Problems

Problem	Difficulty	Link
Single Number	Easy	LeetCode 136
Number of 1 Bits	Easy	LeetCode 191
Counting Bits	Easy	LeetCode 338
Maximum XOR	Medium	LeetCode 421

Interview Tip: XOR is your best friend for “find the unique element” problems. Remember: a ^ a = 0 and a ^ 0 = a.

Interview Questions

1. An array contains n numbers where every element appears twice except one. Find the unique element in O(n) time and O(1) space.

What interviewers are really testing: Whether XOR is your first instinct and whether you can explain the three properties (self-inverse, identity, associativity) that make it work. This is the gateway bit manipulation question. Strong Answer:

XOR all elements together. Every duplicate pair cancels out (a ^ a = 0), and the unique element survives (a ^ 0 = a). One pass, no extra memory.
The three properties that make this work: self-inverse (a ^ a = 0), identity (a ^ 0 = a), and commutativity/associativity (order does not matter, so we can mentally regroup pairs).
Walked example: [4, 1, 2, 1, 2] — XOR all: 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.
Why not a hash set? A hash set works but uses O(n) space. The XOR approach is O(1) space, which is what makes it elegant. Interviewers specifically want to see that you reach for bitwise operations when the constraints demand zero extra space.

Red flag answer: “Use a hash map to count frequencies and find the one with count 1.” That works but uses O(n) space and completely misses the bit manipulation insight the interviewer is testing. Follow-ups:

What if every element appears three times except one? Does XOR still work? What technique handles this?
What if there are two unique elements (everything else appears twice)? How do you separate them using XOR?

2. How does `n & (n - 1)` work, and what problems does it solve?

What interviewers are really testing: Whether you understand the binary-level mechanics of this operation, not just the applications. This one expression solves power-of-two checks, Brian Kernighan’s popcount, and more. Strong Answer:

n - 1 flips the lowest set bit of n and sets all bits below it. So n & (n - 1) turns off the lowest set bit and leaves everything else unchanged. Example: n = 12 (binary 1100), n - 1 = 11 (binary 1011), n & (n-1) = 8 (binary 1000) — the lowest set bit (position 2) got cleared.
Power-of-two check: a power of 2 has exactly one bit set. n & (n - 1) clears that single bit, giving 0. So n > 0 and (n & (n - 1)) == 0 is the O(1) power-of-two test. The n > 0 guard is essential because 0 & (-1) == 0 is also true, but 0 is not a power of 2.
Brian Kernighan’s algorithm: to count set bits (popcount), repeatedly apply n = n & (n - 1) until n becomes 0, counting iterations. Each iteration removes exactly one set bit, so the loop runs exactly popcount(n) times — much faster than checking all 32 bits when the number has few set bits.
This trick also detects whether a number is a power of 4 (must be power of 2 AND have its single set bit in an even position: n & 0x55555555 == n).

Red flag answer: “I memorized that n & (n-1) checks for power of two.” Without being able to explain the bit-level mechanics, the candidate cannot adapt the trick to novel problems. Follow-ups:

How would you count the number of set bits in all integers from 0 to n using the DP recurrence result[i] = result[i & (i-1)] + 1?
What is the Hamming distance between two integers, and how does XOR combined with popcount compute it?

3. Generate all subsets of an array using bitmasks. When is this better than backtracking?

What interviewers are really testing: Whether you can map the concept of subset inclusion/exclusion to binary representation and understand the practical trade-offs versus recursive backtracking. Strong Answer:

Each integer from 0 to 2^n - 1 represents a subset. Bit i being set means “include nums[i].” Iterate through all 2^n masks, and for each mask, iterate through n bits to build the subset. Total time: O(n * 2^n).
Example: for nums = [a, b, c], mask 5 (binary 101) represents [a, c]. Mask 0 is the empty set, mask 7 (111) is the full set.
When it is better than backtracking: the bitmask approach is iterative, so there is no recursion overhead and no risk of stack overflow. It is also easier to reason about correctness — you are guaranteed to enumerate exactly 2^n subsets without duplicates. For n at most 20 (about a million subsets), it is practical and often simpler to code under interview pressure.
When backtracking is better: for large n where you need to prune early (like “subsets with sum at most a target”), backtracking can skip entire branches. Bitmask enumeration always visits all 2^n masks — no pruning possible. Backtracking also generalizes to permutations and combinations, while bitmask is specific to subset enumeration.

Red flag answer: “Bitmask is always better because it avoids recursion.” This ignores the inability to prune and the exponential memory for the bit range. Another red flag is not knowing the practical limit of n at most around 20 for bitmask enumeration. Follow-ups:

How would you enumerate all subsets of size exactly k using bitmasks? What is the trick to go from one k-bit mask to the next lexicographic k-bit mask?
In competitive programming, people use bitmask DP (like Travelling Salesman). How does the bitmask represent the DP state?

4. Explain the difference between signed and unsigned right shift. Why does this matter in bit manipulation interviews?

What interviewers are really testing: Language-level understanding of how negative numbers interact with bitwise operations. This is a frequent source of bugs in Java and C++, and interviewers want to see awareness. Strong Answer:

Arithmetic right shift (>>) preserves the sign bit — it fills new bits on the left with the sign bit (0 for positive, 1 for negative). Logical/unsigned right shift (>>> in Java) always fills with 0, regardless of the sign.
In Java, this distinction is critical. (-1) >> 1 is still -1 (binary all-1s stays all-1s). (-1) >>> 1 is Integer.MAX_VALUE (the sign bit becomes 0). If you are manipulating bits of a negative number and expecting zeros to appear, you must use >>>.
In Python, integers have arbitrary precision, so there is no fixed bit width and >> always does arithmetic shift. Negative numbers in Python are conceptually infinite-width two’s complement, which means ~0 is -1 and bitwise operations on negatives need masking with & 0xFFFFFFFF to simulate 32-bit behavior.
In C/C++, right-shifting a negative number is implementation-defined (the standard does not mandate arithmetic vs. logical). Most compilers do arithmetic shift, but relying on this is technically non-portable. Use unsigned types when doing bit manipulation to avoid surprises.

Red flag answer: “Right shift just divides by 2.” This is true for positive numbers but wrong for negative numbers with logical shift. Another red flag is not knowing that Java has both >> and >>> or that C++ right-shift on negatives is implementation-defined. Follow-ups:

What is two’s complement and why do computers use it instead of sign-magnitude?
What does Integer.MIN_VALUE >> 1 evaluate to in Java? What about Integer.MIN_VALUE >>> 1?

5. Find the missing number in an array containing n distinct numbers from the range [0, n]. Solve it using bit manipulation.

What interviewers are really testing: Whether you can apply the XOR cancellation trick to a slightly different setup. The missing number problem has multiple solutions (math, XOR, sorting), and the XOR approach shows bit manipulation fluency. Strong Answer:

XOR all numbers from 0 to n, then XOR all elements in the array. Every number that appears in both cancels out, leaving only the missing number.
Implementation: initialize result = n, then for each index i, XOR both i and nums[i] into result. After the loop, result is the missing number.
Why this works: the indices 0, 1, ..., n-1 combined with the initial n give us exactly the complete range [0, n]. XOR-ing these with the array elements cancels all present numbers, leaving only the absent one.
Alternative approach: use the sum formula n*(n+1)/2 - sum(nums). This is simpler but can overflow for large n in languages with fixed-width integers. The XOR approach never overflows because XOR does not increase magnitude.

Red flag answer: “Sort the array and look for the gap.” That is O(n log n) and misses the O(n) solutions entirely. The math approach is acceptable, but not mentioning XOR when the question explicitly says “bit manipulation” is a miss. Follow-ups:

What if there are two missing numbers from the range [0, n+1]? Can you still use XOR?
The sum formula n*(n+1)/2 can overflow in 32-bit integers. At what value of n does this happen?

6. How do you add two integers without using the + or - operator? Walk through the bit-level logic.

What interviewers are really testing: Deep understanding of how binary addition works at the hardware level. This problem maps directly to how a CPU’s adder circuit operates. Strong Answer:

Binary addition without a carry is just XOR: 1 + 1 = 0 (with carry), 1 + 0 = 1, 0 + 0 = 0. The carry for each bit position is AND: a carry is generated when both bits are 1.
The algorithm: sum = a ^ b (add without carry), carry = (a & b) << 1 (carry bits, shifted left because a carry at position k affects position k+1). Now add sum and carry — but we cannot use +, so we repeat the process with a = sum, b = carry until there is no carry (b == 0).
In Python, negative numbers require special handling because Python integers have unlimited width. You need to mask with 0xFFFFFFFF to simulate 32-bit arithmetic and convert back from unsigned to signed at the end.
This is literally how a ripple-carry adder works in hardware. XOR gates compute the sum bits, AND gates compute the carry bits, and the carry propagates through the chain. A carry-lookahead adder optimizes this by computing all carries in parallel.

Red flag answer: “Use a - (-b) to avoid the plus sign.” This technically uses subtraction, which is not the spirit of the question. The interviewer wants the XOR/AND loop. Follow-ups:

How do you handle subtraction without the minus operator?
What is the maximum number of iterations the loop can take for 32-bit integers? Why?

7. What are common bit manipulation pitfalls in interviews, and how do you avoid them?

What interviewers are really testing: Practical awareness and defensive coding habits. This is a meta-question that reveals whether the candidate has been burned by these issues before. Strong Answer:

Operator precedence: bitwise operators have lower precedence than comparison operators in Java, C++, and Python. x & 1 == 0 is parsed as x & (1 == 0) = x & 0, not (x & 1) == 0. Always parenthesize: (x & 1) == 0. This bug is almost invisible during interviews.
Integer overflow on shift: 1 << 31 in Java is Integer.MIN_VALUE (negative) because Java uses signed 32-bit ints. For 64-bit shifts, use 1L << n. In C++, 1 << 32 on a 32-bit int is undefined behavior.
The n = 0 edge case: 0 & (0 - 1) equals 0, which passes the power-of-two check, but 0 is not a power of 2. Always guard with n > 0.
Python’s unlimited precision: unlike Java/C++, Python integers grow arbitrarily. ~0 is -1 (not a 32-bit complement). To simulate 32-bit behavior, mask with & 0xFFFFFFFF. This matters for reverse-bits and add-without-plus problems.
Signed vs. unsigned confusion: In Java, there is no unsigned int type. Use >>> for unsigned right shift and Integer.toUnsignedLong() when needed. In C++, mixing signed and unsigned in comparisons triggers compiler warnings for good reason — the implicit conversion can produce surprising results.

Red flag answer: “I have not encountered any issues with bit manipulation.” This means the candidate has not done enough practice. Everyone who has seriously worked with bits has been bitten by precedence or shift-width bugs. Follow-ups:

Write a function to reverse the bits of a 32-bit integer. What is the common off-by-one error people make?
How does the bitset data structure in C++ (or BitSet in Java) differ from manual bit manipulation? When would you use one over the other?

Interview Deep-Dive

When would you choose bit manipulation over a HashMap or sorting-based approach? What are the precise conditions where bit tricks provide an advantage?

Strong Answer:

Bit manipulation wins when the problem involves finding unique elements among duplicates and you need O(1) space. The XOR trick for “find the single number” uses zero extra memory — a HashMap uses O(n) space for the same result.
Condition 1 — Duplicate cancellation. When elements appear in pairs (or triples with bit-counting), XOR or bitwise counting can cancel them without storing anything. This is impossible with sorting (O(n log n) time) or hashing (O(n) space).
Condition 2 — Set representation. When you need to track subsets of a small universe (n less than 32 or 64), bitmasks replace HashSets. Each subset is a single integer, set operations become bitwise OR/AND/XOR, and iteration over subsets uses n & (n-1) tricks. Bitmask DP for TSP (Travelling Salesman) uses this: state is a bitmask of visited cities, which would be an exponentially large set otherwise.
Condition 3 — Arithmetic properties. Problems involving powers of 2, parity, or binary representations are naturally bit-manipulation problems. Checking power of 2 is n & (n-1) == 0 — O(1) versus converting to binary string and counting.
When NOT to use bit manipulation: When the problem has no inherent binary structure, bit tricks become obfuscation rather than optimization. If a HashMap solution is clear and within time/space constraints, prefer readability.
Practical limit: Bitmask approaches work for sets of size up to ~20-25 (since 2^25 = 33 million states). Beyond that, the exponential state space makes bitmask DP infeasible.

Follow-up: In the “Single Number II” problem where every element appears three times except one, XOR alone does not work. What technique do you use instead, and what is the complexity?

You need bitwise counting modulo 3. For each bit position (0 through 31), count how many numbers have that bit set. If the count modulo 3 is 1, the unique number has that bit set; if 0, it does not.
Implementation: use two variables ones and twos that track bits appearing once and twice respectively. The state machine transitions: ones = (ones ^ num) & ~twos, twos = (twos ^ num) & ~ones. After processing all numbers, ones holds the unique number.
Time: O(n). Space: O(1). The modular counting generalizes: for “every element appears k times except one,” count each bit position modulo k.

Explain the bitmask subset enumeration technique. Given a bitmask representing a set, how do you iterate over all subsets of that set in O(2^popcount) time?

Strong Answer:

The trick: To enumerate all subsets of a bitmask mask, start from mask and repeatedly subtract 1 while masking with the original: sub = (sub - 1) & mask. This generates all subsets in decreasing order, terminating at 0.
Why it works: Subtracting 1 from a bitmask flips the lowest set bit and sets all lower bits. ANDing with mask ensures only bits from the original set survive. This systematically generates every combination of bits that are subsets of mask.
Code:

sub = mask
while sub > 0:
    # process subset 'sub'
    sub = (sub - 1) & mask
# also process sub = 0 (empty set) if needed

Complexity: Exactly 2^popcount(mask) subsets are generated, each in O(1) time. If mask has k bits set, this is O(2^k) total. For k = 15, that is 32,768 subsets.
Where this appears: Bitmask DP problems where the transition requires iterating over all subsets of a state. For example, in the “Minimum Cost to Connect Clusters” problem, for each set S of nodes, you try all ways to partition S into two non-empty subsets S1 and S2 where S1 union S2 = S.
Common mistake: Forgetting to handle the empty subset (sub = 0). The loop while sub > 0 excludes it. If you need the empty set, process it after the loop.

Follow-up: In bitmask DP for TSP, the state is dp[mask][i] where mask is the set of visited cities and i is the current city. What is the time complexity, and why is this approach limited to roughly n = 20?

There are 2^n possible masks and n possible current cities, giving 2^n * n states. Each transition tries n-1 possible next cities. Total: O(n^2 * 2^n).
For n = 20: 20^2 * 2^20 = 400 * 1,048,576 = ~419 million operations. Feasible in 1-2 seconds in C++, borderline in Python.
For n = 25: 25^2 * 2^25 = 625 * 33,554,432 = ~21 billion operations. Infeasible on any standard machine.
The exponential 2^n factor is inherent to TSP (NP-hard). Bitmask DP is the standard exact approach for small n.

You are given an array where every element appears twice except two elements that appear once. Find both unique elements using O(1) space.

Strong Answer:

XOR all elements. The result is a ^ b where a and b are the two unique elements. Since a != b, this XOR is non-zero — at least one bit differs between a and b.
Key step: Find any set bit in a ^ b. The simplest way: diff_bit = xor_all & (-xor_all) (isolates the lowest set bit). This bit is set in one of a or b but not both.
Partition the array into two groups: elements with that bit set, and elements without. Each group contains exactly one unique element (because paired elements have the same bits and go to the same group). XOR each group independently to find a and b.
Time: O(n). Space: O(1). Two passes through the array (first to compute XOR, second to partition and XOR each group). Can be done in one pass with careful bookkeeping.
Why this works: The differentiating bit guarantees that a and b land in different groups. All paired elements land in the same group (both copies have the same bit value), so they cancel via XOR within their group.
Edge case: If the two unique elements differ in only the sign bit (one positive, one negative in two’s complement), the algorithm still works because it operates on bit positions, not values.

Follow-up: Can you generalize this to finding three unique elements where everything else appears twice?

XOR all elements gives a ^ b ^ c. You cannot directly extract individual values from a three-way XOR because you do not know which bits belong to which element.
One approach: find a bit where at least one pair of the three unique elements differs. Partition into two groups using that bit. One group has one unique element (solve with simple XOR), the other has two (solve with the two-unique-elements technique above).
This requires careful selection of the differentiating bit and is significantly more complex. In interviews, this is a staff-level follow-up — most interviewers do not expect a complete solution but want to see your reasoning process.

LeetCode Interview Q&A

Four LeetCode-grinder-flavored questions you should be able to answer cold. Each one has a strong-answer framework, full code, senior follow-ups, common wrong answers, and further reading.

Q1: Single Number (LC 136) -- why does XOR work, and how would you generalize it?

Strong Answer Framework

State the three XOR axioms: a ^ a = 0, a ^ 0 = a, XOR is commutative and associative.
Conclude: XORing the entire array regroups duplicates into pairs that cancel, leaving only the unique element.
Note O(n) time, O(1) space.
Mention the natural generalizations: LC 137 (every element appears 3 times) and LC 260 (two unique elements).

Real LeetCode Walkthrough — LC 136

Python

def singleNumber(nums):
    result = 0
    for x in nums:
        result ^= x
    return result

Trace [4, 1, 2, 1, 2]: 0 ^ 4 = 4, 4 ^ 1 = 5, 5 ^ 2 = 7, 7 ^ 1 = 6, 6 ^ 2 = 4. The unique element survives.

Senior follow-up 1: What if every element appears three times except one (LC 137)?XOR alone fails because three copies of a XOR to a, not 0. Use bit-by-bit counting modulo 3, or the elegant two-variable state machine:

Python

def singleNumberII(nums):
    ones = twos = 0
    for x in nums:
        ones = (ones ^ x) & ~twos
        twos = (twos ^ x) & ~ones
    return ones

ones tracks bits seen once mod 3, twos tracks bits seen twice mod 3. After three appearances both reset to 0.

Senior follow-up 2: What if there are two unique elements and everything else appears twice (LC 260)?XOR all elements to get a ^ b. Pick any set bit (e.g., diff = xor_all & -xor_all). Partition the array by that bit — a and b land in different groups, every duplicate pair lands in the same group. XOR each group to recover the two values.

Senior follow-up 3: What if the input is a stream and you cannot store all elements?The XOR approach is already streaming — you only keep result. That is what makes it elegant. Compare with hashing, which requires unbounded memory in the worst case.

Common Wrong Answers

“Use a hash set” — works but is O(n) space; misses the bit-manipulation insight the question is testing.
“Sort and find the lone element” — O(n log n) time, mutates input, also misses the insight.
Using ones / twos for the simple LC 136 case — over-engineered.

Further Reading

LC 137 — Single Number II
LC 260 — Single Number III
LC 268 — Missing Number (same XOR-with-range idea)

Q2: Counting Bits (LC 338) -- why is the DP recurrence dp[i] = dp[i & (i-1)] + 1 elegant?

Strong Answer Framework

Naive: for each i in [0, n], run popcount via Brian Kernighan — O(n log n) total.
Better: notice popcount(i) = popcount(i & (i - 1)) + 1 because i & (i - 1) is i with one set bit removed.
Equivalent recurrence: popcount(i) = popcount(i >> 1) + (i & 1).
Both are O(n) total because each dp[i] is one O(1) lookup plus an addition.

Real LeetCode Walkthrough — LC 338

Python

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

Trace small values:

dp[1] = dp[0] + 1 = 1
dp[2] = dp[0] + 1 = 1
dp[3] = dp[2] + 1 = 2
dp[4] = dp[0] + 1 = 1
dp[5] = dp[4] + 1 = 2

Each dp[i] lookup walks one bit closer to zero — the reason this is O(n) and not O(n log n).

Senior follow-up 1: Can you do it without DP, in O(n) time using a built-in?Yes: [bin(i).count('1') for i in range(n + 1)] works in Python and runs in roughly O(n log n). Most languages have a hardware popcount instruction (Integer.bitCount in Java, __builtin_popcount in C++). The interviewer asking for the DP version is testing whether you can derive the recurrence; saying “use the builtin” misses the point.

Senior follow-up 2: What if n is enormous (say 10^9) but you only need the popcount of a few specific indices?Skip the table entirely and run Brian Kernighan per query. Each query is O(popcount), at most 30 ops for 32-bit ints. Building a table of size 10^9 wastes memory you would not amortize.

Senior follow-up 3: How do you compute popcount of a 64-bit integer in O(1)?Use the SWAR (“SIMD within a register”) parallel-bit-count algorithm: a sequence of mask-and-add steps that combines pair counts, then nibble counts, then byte counts. Or just use __builtin_popcountll — modern x86-64 has a single POPCNT instruction.

Common Wrong Answers

Calling bin(i).count('1') inside the loop and claiming O(n) — string conversion is O(log n).
Returning dp[n] instead of the entire array — misreading the problem.
Off-by-one on the array size (allocating n instead of n + 1).

Further Reading

LC 191 — Number of 1 Bits (single integer popcount)
LC 461 — Hamming Distance (XOR plus popcount)
LC 477 — Total Hamming Distance (per-bit counting)

Q3: Iterate over all subsets of a set using a bitmask -- explain the trick and where it appears.

Strong Answer Framework

Represent the set as a bitmask mask of width n.
To enumerate all 2^n subsets: iterate i from 0 to (1 << n) - 1. Each i is a subset.
To enumerate subsets of a specific mask (not the full universe): use sub = (sub - 1) & mask, starting from sub = mask, until sub rolls over to 0.
Total cost is exactly 2^popcount(mask) iterations — proportional to the number of subsets, not the universe.

Real LeetCode Walkthrough — LC 78 Subsets

Python

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

For nums = [1, 2, 3], masks 0..7 each produce a distinct subset: 000 -> [], 001 -> [1], 010 -> [2], 011 -> [1,2], …, 111 -> [1,2,3].Why subset-of-mask matters: in bitmask DP (e.g., LC 1125 Smallest Sufficient Team, sum-over-subsets DP) you often need to iterate every subset of a given state. The naive double loop for mask in range(1<<n): for sub in range(1<<n): if (sub & mask) == sub is O(4^n). The (sub - 1) & mask trick is O(3^n) total across all masks (each ordered pair (mask, sub) with sub a subset of mask is visited exactly once).

Senior follow-up 1: Why is the total cost O(3^n) for sum-over-subsets DP?For each of the n bits, three states are possible across the (mask, sub) pair: bit is in neither, bit is in mask only, bit is in both. That gives 3^n total ordered pairs, which is exactly what the trick visits.

Senior follow-up 2: How would you generate subsets in lexicographic order instead of bitmask order?Bitmask order is not lex order. For lex order use a Gray code or backtracking with explicit ordering. For LeetCode acceptance, bitmask order is fine — the grader does not care about subset ordering.

Senior follow-up 3: What if n is too large for 2^n (say n equals 40)?Meet-in-the-middle: split the set in half, enumerate 2^{n/2} subsets on each side, combine with hashing or sorting. Bumps the practical limit from around 20 to around 40. See LC 1755 Closest Subsequence Sum.

Common Wrong Answers

Using backtracking and claiming it is O(2^n) better — both are O(n * 2^n); bitmask just removes recursion overhead.
Forgetting mask = 0 (the empty subset) — LC 78 expects it.
Confusing (mask >> i) & 1 (read bit i) with (mask & i) (mask intersect i, very different).

Further Reading

LC 78 / LC 90 — Subsets, Subsets II
LC 1125 — Smallest Sufficient Team (bitmask DP)
LC 691 — Stickers to Spell Word (bitmask BFS)

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

Documentation Index

​What is Bit Manipulation?

​Essential Operations

​Common Tricks

​Pattern Variations

​1. Single Number

​2. Counting Bits

​3. Subsets Using Bitmask

​4. Missing Number

​5. Reverse Bits

​Classic Problems

​Bit Manipulation in DP

​Common Mistakes

​Quick Reference

​Operator and Trick Cheatsheet

​Iterating Subsets of a Bitmask

​Worked LeetCode Problems

​LC 136 — Single Number (Easy)

​LC 191 — Number of 1 Bits (Easy)

​LC 338 — Counting Bits (Easy, DP + bit insight)

​LC 268 — Missing Number (Easy)

​LC 78 — Subsets (Medium, bitmask iteration)

​LC 421 — Maximum XOR of Two Numbers in an Array (Medium, trie + bit greedy)

​Curated LeetCode List

​Practice Problems

​Interview Questions

​1. An array contains n numbers where every element appears twice except one. Find the unique element in O(n) time and O(1) space.

​2. How does n & (n - 1) work, and what problems does it solve?

​3. Generate all subsets of an array using bitmasks. When is this better than backtracking?

​4. Explain the difference between signed and unsigned right shift. Why does this matter in bit manipulation interviews?

​5. Find the missing number in an array containing n distinct numbers from the range [0, n]. Solve it using bit manipulation.

​6. How do you add two integers without using the + or - operator? Walk through the bit-level logic.

​7. What are common bit manipulation pitfalls in interviews, and how do you avoid them?

​Interview Deep-Dive

​LeetCode Interview Q&A

What is Bit Manipulation?

Essential Operations

Common Tricks

Pattern Variations

1. Single Number

2. Counting Bits

3. Subsets Using Bitmask

4. Missing Number

5. Reverse Bits

Classic Problems

Bit Manipulation in DP

Common Mistakes

Quick Reference

Operator and Trick Cheatsheet

Iterating Subsets of a Bitmask

Worked LeetCode Problems

LC 136 — Single Number (Easy)

LC 191 — Number of 1 Bits (Easy)

LC 338 — Counting Bits (Easy, DP + bit insight)

LC 268 — Missing Number (Easy)

LC 78 — Subsets (Medium, bitmask iteration)

LC 421 — Maximum XOR of Two Numbers in an Array (Medium, trie + bit greedy)

Curated LeetCode List

Practice Problems

Interview Questions

1. An array contains n numbers where every element appears twice except one. Find the unique element in O(n) time and O(1) space.

2. How does `n & (n - 1)` work, and what problems does it solve?

3. Generate all subsets of an array using bitmasks. When is this better than backtracking?

4. Explain the difference between signed and unsigned right shift. Why does this matter in bit manipulation interviews?

5. Find the missing number in an array containing n distinct numbers from the range [0, n]. Solve it using bit manipulation.

6. How do you add two integers without using the + or - operator? Walk through the bit-level logic.

7. What are common bit manipulation pitfalls in interviews, and how do you avoid them?

Interview Deep-Dive

LeetCode Interview Q&A