L46 · Bit Manipulation

Series: LeetCode — From Basics to Interview-Ready · Session 46 / 65 · Phase 3 · Advanced & specialised

Why this session exists

XOR cancelling itself is the single most reused bit trick in interviews. x ^ x == 0 and x ^ 0 == x, and XOR is commutative and associative, so if you XOR a whole array together, every value that appears an even number of times vanishes and whatever appears an odd number of times survives. That one fact solves Single Number, finds a missing number, detects a swapped pair, and shows up inside half a dozen harder problems as a subroutine.

The second identity worth burning in is n & (n - 1), which clears the lowest set bit. Subtracting one flips the lowest set bit to zero and turns everything below it into ones; ANDing with the original keeps only the bits above. That gives you a popcount loop proportional to the number of set bits rather than the word size, a power-of-two test in one expression, and the recurrence behind Counting Bits.

Beyond those two, honestly, the returns drop off fast. There are dozens of catalogued bit hacks and almost none of them appear in interviews. I am not going to list them. What I want you to leave with is fluency in three or four identities and, more importantly, the habit of asking "is this a per-bit question" when you see one — because problems about parity, about counting occurrences modulo something, or about sets of small size often are.

The Python-specific wrinkle deserves early warning: Python integers are arbitrary precision and negative numbers behave as if they have infinitely many leading ones. Any problem that says "32-bit signed integer" needs explicit masking in Python, and Sum of Two Integers is unsolvable without understanding that. I will deal with it properly in the guided solve.

Blank-file warm-up

Five minutes, empty file, no notes. Write down and verify by hand:

1. The three XOR facts: x ^ x, x ^ 0, and whether order matters.
2. What n & (n - 1) does, demonstrated on n = 12 in binary.
3. The one-line test for whether n is a power of two, and the edge case it gets wrong.

For step 3: n & (n - 1) == 0 is the test, and it wrongly reports zero as a power of two. The full test is n > 0 and (n & (n - 1)) == 0. That guard is forgotten roughly always.

Pattern anatomy

The shape that summons this pattern: a question that decomposes independently across bit positions, or a counting question where the count matters only modulo something small.

The first shape is why Counting Bits works and why AND-of-a-range works — you can reason about bit 0 without knowing anything about bit 5. The second shape is why XOR works, since XOR is precisely addition modulo 2 done per bit.

Here is the working vocabulary. These are the only ones I would drill:

# --- XOR identities ---
# x ^ x == 0        self-cancellation
# x ^ 0 == x        identity
# a ^ b ^ a == b    commutative and associative, so order never matters
 
def single_number(nums):
    """Every element appears twice except one. Find it."""
    result = 0
    for x in nums:
        result ^= x
    return result
 
# --- lowest set bit ---
# n & (n - 1)  clears the lowest set bit
# n & (-n)     isolates the lowest set bit as a power of two
 
def popcount(n):
    count = 0
    while n:
        n &= n - 1          # runs once per SET bit, not once per bit position
        count += 1
    return count
 
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
 
# --- counting bits for all i up to n, in O(n) ---
def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)      # i's bits = (i//2)'s bits, plus i's last bit
    return dp

The count_bits recurrence is worth staring at. Shifting right by one drops the last bit, so i has exactly the bits of i >> 1 plus whatever the last bit is. Since i >> 1 < i, that value is already computed. The alternative form dp[i] = dp[i & (i - 1)] + 1 is equally valid and says: i has one more set bit than i with its lowest set bit removed.

For masks over a small universe, the operations are the same vocabulary as L44 — set, clear, test, iterate. Bit manipulation and bitmask DP are the same primitives applied at different scales.

The cue

You are looking at a bit-manipulation problem when the statement contains these tells:

1. "Every element appears twice except one" or any parity-flavoured phrasing — once, twice, three times, k times. Even counts vanish under XOR; other counts need the per-bit modular counting variant.
2. "Without using the operators + and -" or a similar restriction on arithmetic. That is a direct instruction to simulate arithmetic with bit logic.
3. "Constant extra space" combined with a counting question. If you would naturally reach for a hash map and the problem forbids extra space, XOR or per-bit accumulation is usually the intended route.
4. "32-bit signed integer" stated explicitly. In Python that phrase is an instruction to mask with 0xFFFFFFFF and to convert back to a signed value at the end.
5. Powers of two, or a question about the binary representation itself — count the ones, reverse the bits, find the position of the single set bit.

Tell 3 is the most useful in practice, because it is the one that fires when the problem has not used any bit vocabulary at all. Constant space plus counting almost always means XOR.

Guided solve

Single Number II — every element appears three times except one, which appears once. Find it, in linear time and constant extra space.

Plain XOR fails here and it is important to see why. XOR is addition modulo 2, so it cancels pairs. Three copies of a value XOR together to give one copy of that value, not zero. The whole array XORed gives you the XOR of every distinct value, which is not what you want.

So generalise the idea rather than the operator. The insight: consider each bit position independently. Across the whole array, if a value appears three times it contributes either three ones or three zeros to that position. So the total count of ones in any bit position is a multiple of three, plus the contribution of the single element. Therefore count_of_ones_at_position_b % 3 is exactly the bit of the answer at position b.

That is a complete algorithm and it is the one I would write first:

def single_number_ii(nums):
    result = 0
    for b in range(32):
        bit_sum = 0
        for x in nums:
            bit_sum += (x >> b) & 1
        if bit_sum % 3:
            result |= 1 << b
    # convert from unsigned 32-bit back to signed
    if result >= 1 << 31:
        result -= 1 << 32
    return result

O(32n) time, which is O(n), and O(1) space. Clean, explicable, and you can derive it at the whiteboard from first principles rather than recalling it.

The sign fix-up at the end is the Python trap. If the answer is negative, the per-bit reconstruction produces its unsigned 32-bit representation — a large positive number. Subtracting 2^32 when the value has the sign bit set converts it back. Forget this and negative test cases fail while positive ones pass.

There is a well-known constant-time-per-element version using two accumulators, ones and twos, that tracks each bit's count modulo three in two bits of state:

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

I would not write this from memory in an interview unless I could also explain it, and explaining it takes a minute of careful reasoning about the state machine each bit position is running. Know that it exists. Write the modulo-3 version.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Single Number — the pure XOR one-liner. Should take under two minutes; if it does not, the warm-up did not stick.
• Counting Bits — return the popcount for every integer from 0 to n. Aim for the O(n) DP recurrence rather than calling a builtin per number, and be able to state the recurrence in words.
• Sum of Two Integers — no + or -. Budget the full fifteen minutes and expect the masking to bite. Test with one negative operand before you consider it done.
• Happy Number — not a bit problem at all, but a cycle-detection one. Included here because it often appears in the same problem set and the right answer is Floyd's tortoise and hare.

Common failure modes

Assuming XOR handles counts other than two. It only cancels even multiplicities. Three copies leave one copy behind. Reach for per-bit modular counting whenever the multiplicity is not two.

Missing the n > 0 guard on the power-of-two test. 0 & -1 == 0, so zero reports as a power of two. One-character-class bug, appears constantly.

Forgetting the 32-bit mask in Python. Any problem stating "32-bit signed" needs & 0xFFFFFFFF inside the loop, and a signed conversion at the end. Without the mask, carry-propagation loops never terminate on negative inputs — an infinite loop rather than a wrong answer, which at least is loud.

Right-shifting a negative number and expecting sign truncation. In Python, -1 >> 1 is -1, forever. Negative integers behave as if they have infinitely many leading ones, so a loop of the form while n: n >>= 1 never terminates for negative n. Mask first.

Operator precedence. &, |, and ^ all bind looser than comparison operators in Python, so a & b == 0 means a & (b == 0). Parenthesise every bitwise expression that participates in a comparison. This bug is silent.

Reaching for bit tricks when a hash map is clearer. If the problem does not constrain space and does not mention bits, a counter is more readable and equally fast. Cleverness that is not required is a cost, not a benefit.

Complexity

XOR over an array: O(n) time, O(1) space. One pass, one accumulator, one operation per element. There is no way to do better since you must look at every element.

Per-bit counting for Single Number II: O(32n) = O(n) time, O(1) space. The 32 is a constant determined by the integer width, not by the input, so it is correctly dropped from the asymptotic bound — but it is a real factor of 32 in practice, and worth mentioning to the interviewer rather than pretending it is free.

n & (n - 1) popcount: O(number of set bits), which is at most 32 for a 32-bit integer but is often far fewer. Compare with the naive shift loop, which is always exactly the bit width.

Counting Bits DP: O(n) time, O(n) space — one array entry per integer, each computed in constant time from an already-computed smaller index.

Sum of Two Integers: O(1) — the carry loop runs at most 32 times, once per bit position, because each iteration moves the carries strictly leftward.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Track the identities separately from the problems. Remembering that Single Number is XOR is not the same as being able to state why n & (n - 1) clears the lowest bit, and the second decays faster.