Bit Manipulation

Review boundary and corrected contracts

Multiplication, division and shifts have different language semantics, especially for negative values and / returning float. CPython bytecode dispatch and arbitrary-precision arithmetic make blanket machine-code equivalence claims inappropriate. Choose bit operations for their bit-level meaning and benchmark only when needed.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own the small set of bit identities that actually recur — XOR self-cancellation, lowest-set-bit clearing, and bitwise addition — and know which problems they unlock.

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

Prerequisites. Binary representation and the operators AND, OR, XOR, NOT and shift. No prior session required — this one is self-contained, though L33 helps for the Counting Bits recurrence.

Watch first

Optional original video resources (not prerequisites for the worked examples):

• Bitwise Operations tutorial #1 — XOR, Shift, Subsets — Errichto Algorithms. The operators themselves, properly, including subset enumeration over a bitmask — the foundation the LeetCode problems assume you already have.
• Single Number — Leetcode 136 — NeetCode. XOR self-cancellation in its purest form, which is the single most reused bit fact in practice.
• Counting Bits — Dynamic Programming — Leetcode 338 — NeetCode. Where n & (n - 1) becomes a DP recurrence — the clearest payoff for learning the clear-lowest-set-bit identity.

Why this session exists

XOR cancelling itself is the single most reused bit trick in practice. 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, helps separate two singletons, 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 practice. 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.

Python integers have unbounded precision and sign-extending bit operations. Fixed-width simulation may require a mask; the finite per-bit reconstruction below instead inspects 32 specified positions and restores a signed result.

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):
    if n < 0:
        raise ValueError("popcount here requires a nonnegative integer")
    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.

Two singletons and subset enumeration

When exactly two distinct values appear once and all others twice, XOR the array to obtain a ^ b. Its lowest set bit distinguishes a from b. Partition the input by that bit and XOR each side; paired values go to the same side and cancel. This also works for negative Python integers without imposing a width.

def two_singletons(nums):
    combined = 0
    for x in nums:
        combined ^= x
    bit = combined & -combined   # nonzero: the two singletons are distinct
    left = right = 0
    for x in nums:
        if x & bit:
            left ^= x
        else:
            right ^= x
    return left, right

For Missing Number, XOR the values with every index from 0 through n: all present values cancel and only the missing one remains. This is a different contract from the two-singleton problem; a duplicate-and-missing task needs its own frequency contract. Swapping positions alone leaves the total XOR unchanged, so detecting misplaced positions requires positional information.

For subsets of n distinct positions, iterate mask from 0 through (1 << n) - 1 and include position i exactly when mask & (1 << i) is nonzero. Producing all subsets explicitly requires Θ(n·2^n) output elements in total for positive n; compact masks do not make that output cost disappear.

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. Decide whether you are modelling a fixed-width operation. Mask a wrapping carry loop; a finite 32-position bit scan can inspect signed inputs directly and convert its reconstructed result. XOR cancellation works on Python signed integers without a mask.
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 a uniform parity contract suggests XOR; other counting contracts may need a different summary.

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

For signed 32-bit inputs, O(32n) word operations and O(1) auxiliary numeric variables. The width restriction matters: values outside that domain are truncated to their low 32 bits by this reconstruction, unlike the arbitrary-width two-accumulator version below.

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

For each bit, (ones, twos) cycles through (0,0) → (1,0) → (0,1) → (0,0) when that input bit is one, and stays put when it is zero. The second assignment deliberately reads the new ones. This invariant also applies to sign-extended negative Python integers, so the fast version needs no 32-bit mask and can handle arbitrary-sized signed values. The finite scan above instead requires signed 32-bit inputs.

For Sum of Two Integers without +: a ^ b gives the sum of each bit position ignoring carries, and (a & b) << 1 gives exactly the carries. Loop until there is no carry left. In Python you must mask to 32 bits every iteration with & 0xFFFFFFFF, because the unmasked loop on a = −1, b = 1 produces (−2, 2), (−4, 4), and so on forever. Some other negative pairs terminate; the mask guarantees bounded-width behavior for every pair. Then convert the result back to signed at the end. This problem is genuinely harder in Python than in Java, and saying so to a reviewer is fair.

Carry-loop implementation

This returns the signed 32-bit wrapping sum. If the mathematical sum lies outside the signed range, wrapping is the specified behavior here, not arbitrary-precision addition. The conversion uses no plus or minus operator.

def add32(a, b):
    mask = 0xFFFFFFFF
    a, b = a & mask, b & mask
    while b:
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    return a if a < 0x80000000 else ~(a ^ mask)

The invariant is that a + b is the original sum modulo 2^32. XOR supplies non-carry bits and the shifted AND supplies carries; simultaneous assignment uses both old operands. Each nonzero carry's lowest set position moves left, so at most 32 iterations remain after the initial masking. For (−1, 1), the carry eventually leaves bit 31 and the result is zero.

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. Fixed-width carry or overflow simulation needs & 0xFFFFFFFF inside the loop, and a signed conversion at the end. Without the mask, an unmasked carry loop can fail to terminate, for example on a = −1, b = 1 — 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. Python shifts bind tighter than &, then ^, then |; all of them bind tighter than comparisons. Thus a & b == 0 means (a & b) == 0. Parentheses help readers but are not required to fix that grouping.

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.

Myth: Bit manipulation makes code faster, so preferring bitwise operations over arithmetic is a good general optimisation.

Multiplication, division and shifts have different language semantics, especially for negative values and / returning float. CPython bytecode dispatch and arbitrary-precision arithmetic make blanket machine-code equivalence claims inappropriate. Choose bit operations for their bit-level meaning and benchmark only when needed.

Steps 1: Because XOR on a single bit returns 1 exactly when the two inputs differ, it is addition modulo 2.

Steps 2: Because addition modulo 2 is commutative and associative, XORing a list of values gives a result independent of order.

Steps 3: Because any value XORed with itself is 0 under that arithmetic, every value appearing an even number of times contributes nothing to the total.

Steps 4: Because the identity element is 0, whatever remains after all even-multiplicity values cancel is exactly the XOR of the odd-multiplicity values.

Steps 5: Because subtracting 1 from n flips the lowest set bit to 0 and sets every bit below it, ANDing with n retains only the bits strictly above that position — clearing exactly one set bit per operation.

Steps 6: Therefore a popcount loop using n &= n - 1 runs once per set bit, and the testable prediction is that counting bits of 2^31 takes one iteration while counting bits of 2^31 - 1 takes thirty-one, despite the two numbers differing by one.

Picture: A row of light switches, one per bit, and every number in the array walks past flipping the switches where it has a 1. A value that walks past twice leaves every switch exactly as it found it. At the end, the switches still on spell out whatever walked past an odd number of times.

Trigger: Fires on any problem about counts modulo a small number, parity, or a property that can be decided one bit position at a time.

Name: XOR / per-bit counting

Gain: O(1) word storage for fixed-width inputs and a small invariant when the multiplicity contract matches; the finite bit scan makes 32 passes

Cost: Only applies when the counting structure is modular; must distinguish a fixed-width scan from arbitrary-width XOR and from wrapping addition; the invariant needs explanation

Name: Hash map counter

Gain: Works for any multiplicity, any value range, negative numbers included, with no masking; immediately readable by anyone

Cost: Up to O(n) dictionary entries, which may violate a constant-space requirement; elapsed speed versus bit loops depends on the runtime and inputs

Pick: Use XOR or per-bit counting when the problem explicitly demands constant extra space, or when multiplicities are uniform and known. Use a hash map when multiplicities vary per element, when the value domain is unbounded, or when the problem places no space constraint and readability is worth more than the space saved.

Memory hook — the four identities, and nothing else

Resist learning a catalogue. Four identities cover the examples in this session, and each has a one-line justification you can reproduce on a whiteboard.

1. x ^ x = 0, x ^ 0 = x — XOR is a self-cancelling toggle. Because it is commutative and associative, XORing a whole array erases everything that appears an even number of times. The peg: "pairs vanish."
2. n & (n - 1) clears the lowest set bit — subtracting one flips the lowest set bit to zero and sets everything below it, so the AND keeps only the bits above. The peg: "minus one borrows down, AND wipes the borrow."
3. n & -n isolates the lowest set bit — the two's-complement negation is the complement plus one, which leaves exactly that one bit agreeing. The peg: "negate to isolate."
4. a ^ b is sum-without-carry, (a & b) << 1 is the carry — together they are a full adder, looped until the carry is empty. The peg: "XOR adds, AND carries."

The umbrella mnemonic is "pairs vanish, minus-one wipes, negate isolates, XOR adds." Four clauses, four identities, in increasing order of how often you need them.

And one Python-specific peg that is not an identity but will cost you a submission: "32 bits means mask." Python integers are unbounded and negatives behave as if they carry infinitely many leading ones, so fixed-width overflow simulation requires & 0xFFFFFFFF inside the loop and an explicit signed conversion at the end.

What reviewers actually ask

Bit problems cluster at the easy end and are usually asked as warm-ups or as the second question when time remains — with the exception of Sum of Two Integers, which is a genuine filter in Python.

• 136 · Single Number (Easy) — Practice selection. Probing whether you know XOR cancels. Follow-up: 137 · Single Number II (three copies) and 260 · Single Number III (two singletons, split by an isolated differing bit).
• 191 · Number of 1 Bits (Easy) — Practice selection. Probing the n & (n - 1) loop rather than a 32-iteration scan. Follow-up: "what if the input is very sparse?" — that is exactly why the identity wins.
• 338 · Counting Bits (Easy) — Practice selection. Probing whether you build a DP off a bit identity instead of calling popcount n times. Follow-up: justify the recurrence.
• 190 · Reverse Bits (Easy) — Practice selection. Probing careful shift bookkeeping over a fixed 32 iterations. Follow-up: "what if this is called many times?" — cache by byte.
• 371 · Sum of Two Integers (Medium) — Practice selection. Probing the full-adder loop plus, in Python, the masking discipline. This one separates people.
• 268 · Missing Number (Easy) — Practice selection. Probing that XOR of indices against values cancels everything but the gap. Follow-up: the Gauss-sum solution and why XOR avoids overflow in fixed-width languages.
• 78 · Subsets (Medium) — Practice selection. Probing bitmask enumeration: iterate a counter from 0 to 2^n and read its bits as membership.

The common escalation is "now do it in constant extra space" — which prompts checking whether the count contract really permits a parity summary such as XOR.

Complexity

XOR over an array: O(n) time, O(1) word space for bounded-width integers. With arbitrarily large Python integers, each bitwise operation and accumulator uses storage/work depending on operand bit length; these are word-operation bounds, not constant-bit-cost guarantees.

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 a reviewer 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. A fixed-width scan uses 32 positions; while n: n >>= 1 on nonnegative n uses its bit_length, not always 32.

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.

You can now…

• Recall the four identities — pairs vanish, minus-one wipes, negate isolates, XOR adds — and justify each in one line.

• Solve Single Number and Missing Number, and partition two singletons by a differing bit; explain why XOR alone cannot detect swapped positions.

• Use n & (n - 1) for a popcount loop proportional to set bits, and guard the power-of-two test against zero.

• Generalise from XOR to per-bit counting modulo k when values repeat k times instead of twice.

• Mask wrapping 32-bit carry arithmetic; distinguish it from XOR cancellation and a finite per-bit scan, which need no input mask.

• Implement addition with the XOR-and-carry loop and explain why it terminates once masked.

• Recognise bitmask subset enumeration as the tool when n is small enough that 2^n is tractable.

Quiz

Self-check (answer follows each question).

Q: Why does XOR solve Single Number but not Single Number II?

A: XOR is addition modulo 2, so it cancels even multiplicities. With three copies of each value, three XORs leave one copy behind rather than zero. Multiplicity 3 needs per-bit counting modulo 3 instead.

Q: What does n & (n - 1) do, and why does subtracting one produce that effect?

A: It clears the lowest set bit. Subtracting 1 flips that bit to 0 and turns every bit below it to 1; ANDing with the original keeps only the bits above, discarding the lowest set bit and everything under it.

Q: What is wrong with return (n & (n - 1)) == 0 as a power-of-two test?

A: It returns True for n = 0, which is not a power of two. The correct test is n > 0 and (n & (n - 1)) == 0.

Q: Why does Sum of Two Integers require masking with 0xFFFFFFFF in Python?

A: The unmasked update on (−1, 1) repeats (−2, 2), (−4, 4), … because carries can reach arbitrarily high sign bits. Masking every update to 32 bits discards carry beyond bit 31 and guarantees termination. This does not mean every negative pair loops forever or every signed-integer algorithm requires a mask.

Q: State the Counting Bits recurrence and explain it in one sentence.

A: dp[i] = dp[i >> 1] + (i & 1). Right-shifting drops the last bit, so i has exactly the set bits of i >> 1 plus its own last bit, and i >> 1 is smaller so it is already computed.

Q: You have an array of n distinct numbers drawn from 0 to n, with exactly one missing. Give an O(n) time, O(1) space solution using XOR.

A: XOR together every array element and also every integer from 0 to n. Each present value appears exactly twice across the two sequences and cancels; the missing value appears only once in the index sequence and survives as the result.

Stretch: true

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.

• XOR is addition modulo 2 per bit: self-cancelling, order-independent, and it is the whole of Single Number.

• For multiplicity k other than 2, count ones per bit position and take the count modulo k.

• n & (n - 1) clears the lowest set bit — popcount in set-bit time, plus the power-of-two test with the n > 0 guard.

• Counting Bits is dp[i] = dp[i >> 1] + (i & 1), which is one line and O(n).

• In a wrapping 32-bit carry loop, mask every update and convert back to signed. Ordinary XOR on signed Python integers does not require that mask.

• Python bitwise operators bind tighter than comparisons; shifts bind tighter than &. Parenthesize for readability, not because (n & mask) == 0 would otherwise parse differently.

Corrective source notes

• Built-in Types — Python 3.14.8 documentation — Python integer bitwise operations behave with infinite sign extension, so negative right shifts do not truncate to zero. Checked 2026-10-07.

• Python 3.14 reference — Operator precedence — Python shifts bind tighter than bitwise AND, and bitwise AND binds tighter than comparisons. Checked 2026-10-07.

• Python 3.14 bitwise integer semantics and operator precedence — infinite sign extension, right shift as floor division, and bitwise operators above comparisons. Freshly checked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.