Notes

Bit Manipulation

11 min read

nice-to-have mid · part of Skills & Topics · Senior SWE Roadmap · related: Arrays & Strings · Hashing & Hash Maps · Backtracking · Dynamic Programming

Why this matters / recognition signals

Bit manipulation problems exploit the fact that integers are already a compact array of bits — XOR, AND, OR, and shifts let you do set operations, parity checks, and subset enumeration in O(1) per operation with no extra memory, where an array/hash-map based solution would need O(n) space. It’s a smaller slice of interviews than arrays/hashing, but when it’s the intended solution, the array/hash-map approach is usually the “obviously correct but not optimal” answer, and naming the bit trick is exactly the signal that separates a mid-level from a senior-level solution.

Reach for it when the problem says:

  • “Every element appears twice except one” / “find the single element” → XOR (self-canceling pairs).
  • “Count the number of 1 bits” / “is this a power of two” → n & (n-1) clears the lowest set bit.
  • “Represent a subset / visited state compactly” (often alongside n ≤ 20 in the constraints, a strong tell) → bitmask, one bit per element.
  • “Do this without extra space” where the values involved are small integers or booleans → a bitmask can replace a boolean[] or Set<Integer> with a single int/long.
  • “Swap without a temp variable” / “check if two numbers have opposite signs” → classic bitwise-identity party tricks, rarely the whole problem but worth recognizing.

Core mechanism: bits as a compact set

Every integer is a fixed-width sequence of bits. The operations that matter:

OpSymbolEffect
AND&1 only where both bits are 1 — used to test/clear specific bits
OR|1 where either bit is 1 — used to set specific bits
XOR^1 where bits differ — used to toggle bits, and to cancel out equal values
NOT~flips every bit
left shift<<multiply by 2 per shift; also used to build a mask (1 << i)
right shift>>divide by 2 per shift (careful with sign-extension on negative numbers)

n & (n-1): clear the lowest set bit

Subtracting 1 from n flips every trailing zero to a 1, and the lowest set bit to a 0 (borrow propagates through all the trailing zeros). ANDing with the original n keeps everything above that bit unchanged, but zeroes out that lowest set bit specifically — because everything below it is now guaranteed to differ from n.

Worked trace: n = 12 (binary 1100).

StepValueBinary
n121100
n - 1111011
n & (n-1)81000

The lowest set bit (the 4’s place, value 4) is cleared; the 8’s place bit is untouched. Repeating this operation until the value hits 0 counts exactly one set bit per iteration — an O(popcount) loop instead of an O(bit-width) loop that checks every bit whether set or not.

flowchart LR
    N["n = 1100 (12)"] --> Sub["n - 1 = 1011 (11)<br/>borrow flips trailing zeros to 1,
flips the lowest set bit to 0"]
    Sub --> And["n & (n-1) = 1000 (8)<br/>lowest set bit cleared,
everything above unchanged"]

A direct corollary: n & (n-1) == 0 iff n is a power of two (or zero) — a power of two has exactly one set bit, so clearing “the lowest set bit” clears the only one, leaving 0.

XOR to find the single non-duplicate

XOR has two properties that combine into a trick: x ^ x = 0 (a value cancels itself), and XOR is commutative/associative, so the order of operations doesn’t matter. XOR every element of an array where every value appears exactly twice except one — every pair cancels to 0, leaving only the unpaired value.

Worked trace: [4, 1, 2, 1, 2].

StepRunning XORBinaryElement XORed in
start0000—
141004
251011
371112
461101 (partially cancels the earlier 1)
541002 (cancels the earlier 2)

Group by commutativity to see why: 4 ^ 1 ^ 2 ^ 1 ^ 2 = (1^1) ^ (2^2) ^ 4 = 0 ^ 0 ^ 4 = 4. The final value is 4 — the single non-duplicate — computed in O(n) time and O(1) space, versus a hash-set approach that’s also O(n) time but O(n) space.

flowchart LR
    A["4"] -->|"^"| B["1"]
    B -->|"^"| C["2"]
    C -->|"^"| D["1"]
    D -->|"^"| E["2"]
    E --> R["result = 4"]
    Note["pairs cancel regardless of order:
(1^1)=0, (2^2)=0, leaving 4^0^0 = 4"]

Bitmasks for subsets and visited state

A single integer can represent a set of up to (bit-width) elements: bit i set means “element i is in the set.” This replaces a boolean[] or a Set<Integer> with one primitive value, which is both faster (no allocation, no hashing) and directly usable as a memoization key in bitmask DP.

OperationExpression
Add element i to the setmask | (1 << i)
Remove element imask & ~(1 << i)
Check if i is in the set(mask >> i) & 1 (or mask & (1 << i)) != 0)
Toggle element imask ^ (1 << i)
Full set of n elements(1 << n) - 1
Is the set emptymask == 0

Worked trace — building up the set {0, 2, 3} out of 4 possible elements, one bit per element (bit 0 = element 0, reading right to left):

StepOperationMask (binary)Set contents
0start0000{}
1add 0 → mask | (1<<0)0001{0}
2add 2 → mask | (1<<2)0101{0, 2}
3add 3 → mask | (1<<3)1101{0, 2, 3}
4remove 2 → mask & ~(1<<2)1001{0, 3}

This is the reason n ≤ 20 in a problem’s constraints is a strong tell for a bitmask-DP solution: 2^20 ≈ 10⁶ possible subset states is exactly the range where “iterate over all subsets, keyed by an int bitmask” is both correct and fast enough (see Dynamic Programming for bitmask DP itself, and Backtracking for the closely related “visited set” use during subset/permutation search).

Java implementation — Single Number & Counting Set Bits

// XOR trick: every element appears twice except one — O(n) time, O(1) space
public int singleNumber(int[] nums) {
    int result = 0;
    for (int n : nums) {
        result ^= n;
    }
    return result;
}
 
// n & (n-1) clears the lowest set bit each iteration — loop runs once per set bit
public int countSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);   // clear lowest set bit
        count++;
    }
    return count;
}
 
public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Python implementation — Single Number & Counting Set Bits

from functools import reduce
import operator
 
def single_number(nums: list[int]) -> int:
    """XOR trick: every element appears twice except one — O(n) time, O(1) space."""
    return reduce(operator.xor, nums, 0)
 
 
def count_set_bits(n: int) -> int:
    """n & (n-1) clears the lowest set bit each iteration."""
    count = 0
    while n != 0:
        n &= (n - 1)
        count += 1
    return count
 
 
def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

bin(n).count("1") and Python 3.10+‘s n.bit_count() do the same popcount in a single call — worth naming as the idiomatic real-world choice, while still knowing the n & (n-1) trick by hand since that’s what’s actually being asked for in an interview.

Complexity comparison

ApproachTimeSpaceWhy
Single Number — hash set (add/remove on each occurrence)O(n)O(n)Needs to track which values have been seen
Single Number — XORO(n)O(1)Pairs self-cancel; no auxiliary storage needed
Count set bits — check every bit positionO(bit-width) e.g. O(32)O(1)Tests all 32 bits regardless of how many are actually set
Count set bits — n & (n-1) loopO(popcount) ≤ O(bit-width)O(1)Loop runs exactly once per set bit, skips runs of zeros
Subset/visited state — boolean[] or HashSet<Integer>O(1) per opO(n)Allocated array/hash structure
Subset/visited state — bitmask (int/long)O(1) per opO(1) (one primitive)Whole set lives in one machine word, up to 32/64 elements

Common pitfalls

  • Right-shifting negative numbers with >> in Java expecting zero-fill: Java’s >> is an arithmetic shift — it sign-extends, filling with the sign bit, not zero. Use >>> (unsigned/logical shift) when you specifically need zero-fill on a negative or when treating the value as raw bits rather than a signed number. Python has no >>> — int is arbitrary-precision with no fixed sign bit in the same sense, so shifting behaves differently and this specific bug doesn’t translate directly, but it’s still worth knowing which language you’re in.
  • Off-by-one on which bit is “bit 0”: 1 << i sets bit i counting from the least significant bit as 0. Mixing this up with 1-indexed element numbering is a common source of “works for the example, wrong for edge elements” bugs.
  • Forgetting operator precedence around bitwise operators: & and ^ bind looser than == and comparison operators in both Java and Python — if (mask & 1 == 1) in a language where this matters parses as mask & (1 == 1), not (mask & 1) == 1. Always parenthesize bitwise sub-expressions explicitly.
  • Using the XOR trick when the “except one” invariant doesn’t actually hold: it specifically requires every other element to appear an even number of times (classically exactly twice) — if the problem is “every element appears three times except one,” plain XOR does not work (each value would need to cancel after 3 occurrences, which requires a different bit-counting-per-position technique, not simple XOR).
  • Assuming a bitmask fits in a 32-bit int without checking n: a bitmask representing n elements needs n bits — safe in a 32-bit int only up to n ≤ 31 (leaving the sign bit out of trouble); beyond that, use long (Java, up to 63 usable bits) or Python’s arbitrary-precision int (no ceiling, but each extra bit still costs real time/space once numbers get large).
  • Reaching for bit tricks when they don’t actually help: n & (n-1) and friends are elegant, but if the array/hash-map version is equally fast asymptotically and the bit version doesn’t save space in a way that matters, defaulting to the more readable version is the better interview answer — cleverness for its own sake reads as a red flag, not a strength.

Practice problems

  • Single Number (XOR — every element twice except one)
  • Single Number II / III (variants: every element three times except one; two elements appear once — both need more than plain XOR, good follow-ups to probe depth)
  • Number of 1 Bits / Counting Bits (popcount via n & (n-1), and the O(n) DP relation bits[i] = bits[i >> 1] + (i & 1) for the range version)
  • Power of Two / Power of Four (n & (n-1) == 0, plus an extra mask check for “power of four” to distinguish it from power of two)
  • Missing Number (XOR of 0..n against the array — same cancellation idea as Single Number, applied to detect what’s absent rather than what’s unpaired)
  • Subsets (bitmask enumeration: iterate mask from 0 to (1<<n)-1, each mask directly encodes one subset — bridges to Backtracking)
  • Traveling Salesman-style bitmask DP (state = (mask, position), mask tracks visited cities — bridges to Dynamic Programming)

Interview angles

  • “Why does XOR find the single non-duplicate, precisely?” — state both properties explicitly: x ^ x = 0 (self-cancellation) and XOR’s commutativity/associativity (order doesn’t matter, so all the paired duplicates group together and cancel regardless of array order), leaving only the unpaired value.
  • “What if every other element appears three times instead of two?” — plain XOR breaks (three copies don’t cancel to 0); the fix tracks, per bit position, the count of 1s across all numbers mod 3 — a meaningfully harder problem, good to at least name the direction (bit-position counting, or a two-variable “ones/twos” state machine) even without producing the full solution live.
  • “Why is n & (n-1) faster than checking each bit?” — it does one operation per set bit, not per bit-width position; for a sparse number (few set bits) this is meaningfully fewer iterations than a fixed 32-iteration loop, though both are technically O(1) for a fixed-width integer — the honest framing is “fewer iterations in practice, same asymptotic bound for a fixed-width type.”
  • “When would you use a bitmask instead of a Set<Integer>/boolean[]?” — when the universe of elements is small and bounded (commonly signaled by n ≤ 20 or so in constraints) and you need the state itself to be a cheap, hashable, comparable value — e.g. as a memoization key in bitmask DP, where a Set would need a custom hash/equals and be slower to copy/compare.
  • “Is bit manipulation ever not the right call even when it’s possible?” — yes: if it doesn’t improve the asymptotic complexity and only saves a small constant factor of space at the cost of readability, prefer the more obvious array/hash-map solution — flag this trade-off explicitly rather than defaulting to “clever” as if it’s automatically better.
  • “How would you check if two integers have opposite signs without a branch?” — (a ^ b) < 0 — XOR of two numbers with different sign bits has its sign bit set, giving a negative result; a good micro-example of reading the sign bit directly instead of branching on >/< comparisons.

My Notes

Graph View