Bit Manipulation

Bit manipulation is a small toolkit — six operators and perhaps four identities — that shows up in a narrow but memorable set of problems. It rarely turns an impossible problem into a possible one. What it does is replace a data structure with arithmetic: the hash set you were going to allocate becomes a single integer, and O(n) space becomes O(1).

The operators#

Everything here is one of six things, applied to numbers you have stopped thinking of as numbers and started thinking of as rows of bits.

• a & b — and: 1 only where both are 1. Used to keep bits.
• a | b — or: 1 where either is 1. Used to add bits.
• a ^ b — xor: 1 where the two differ. Used to flip bits.
• ~a — not: every bit inverted.
• a << k — shift left: bits move up k places, the low end filled with zeros.
• a >> k — shift right: bits move down k places; what fills the top is the subtle part.

Two of those deserve a sentence more. x << k multiplies by 2ᵏ and x >> k divides by 2ᵏ rounding down — which for negative numbers is not the same as the division your language’s / performs. And ~ is best remembered by its arithmetic identity, ~x == -x - 1, which is what falls out of two’s complement representation.

The four identities worth memorising:

x ^ x == 0          // anything cancels itself
x ^ 0 == x          // 0 is the identity, so an accumulator starts there
x & (x - 1)         // clears the lowest set bit
x & -x              // isolates the lowest set bit, discarding the rest

The first two make XOR an accumulator that forgets things in pairs. The last two are why bit counting is a loop over set bits rather than a loop over all 32 positions.

XOR: the self-cancelling accumulator#

XOR is commutative and associative, so a chain of them can be reordered freely. Combine that with x ^ x == 0 and something useful follows: fold an entire array with XOR and every value that appears an even number of times vanishes, regardless of where it sat.

Watch the accumulator rather than the array. Each value flips exactly the bits it has set; when the same value comes round again it flips those same bits back off. The order never matters, which is why no sorting and no bookkeeping is needed — by the end, only the unpaired value’s bits are still standing.

acc = 0                  // identity for XOR

for x in nums:
    acc = acc ^ x        // pairs cancel, wherever they are

return acc               // whatever had no partner

The invariant is worth stating: acc is always the XOR of everything seen so far, which is exactly the values that have so far appeared an odd number of times. At the end, “so far” is the whole array.

The alternative solution is a hash set — add on first sight, remove on second, see what is left. That works and is easier to explain, and it costs O(n) memory. XOR is the same answer in one integer.

Missing Number is the same problem#

Given the numbers 0..n with exactly one removed, XOR together both the full range and the array. Every value present in the array appears twice across that combined fold — once from each side — and cancels. The missing one appears only once, from the range.

acc = 0

for i = 0 .. n:
    acc = acc ^ i        // every index in the complete range

for x in nums:
    acc = acc ^ x        // every value actually present

return acc               // the one that never got a partner

The summation trick — n(n+1)/2 minus the actual sum — also solves it, and the XOR version is the one that cannot overflow. Worth mentioning out loud if the interviewer sets a large n.

Masks: reading and writing single bits#

When a problem cares about one specific position, build a mask with 1 << i — an integer with a single 1 bit — and combine it. These four are the entire vocabulary:

test  =  (x >> i) & 1        // 1 if bit i is set, else 0
set   =  x | (1 << i)        // turn bit i on, leave the rest alone
clear =  x & ~(1 << i)       // turn bit i off
flip  =  x ^ (1 << i)        // toggle bit i

The pattern behind them is worth seeing rather than memorising: | can only ever turn bits on, & with an inverted mask can only turn them off, and ^ is the one that changes a bit without needing to know what it was.

A mask can also stand for a whole subset. With n items, the integers 0 .. 2ⁿ − 1 enumerate every subset exactly once, bit i meaning “item i is in”. That turns generating all subsets into a double loop with no recursion at all — the iterative answer to Subsets, and a useful trick to have when a backtracking solution would be more code than the problem deserves.

for mask = 0 .. (1 << n) - 1:
    subset = empty
    for i = 0 .. n - 1:
        if (mask >> i) & 1:
            add items[i] to subset
    emit subset

Counting set bits#

The obvious loop checks all 32 positions. The better one uses x & (x - 1), which clears the lowest set bit and nothing else — so the loop runs once per set bit rather than once per position.

Why it works is worth a look, because the same subtraction shows up elsewhere. Subtracting 1 turns the lowest 1 into a 0 and every 0 below it into a 1; everything above is untouched. ANDing that against the original therefore keeps the high part and wipes out the bottom:

x        = 1011_0100
x - 1    = 1011_0011      // lowest 1 flipped off, the 0s below it flipped on
x & (x-1)= 1011_0000      // lowest set bit gone

count = 0

while x != 0:
    x = x & (x - 1)      // remove one set bit per iteration
    count = count + 1

return count

This is Brian Kernighan’s algorithm, and its cost is O(number of set bits) — at most the word size, usually far less.

The same identity gives Counting Bits, where you need the popcount of every number from 0 to n. Since i & (i - 1) is a strictly smaller number, its answer is already computed:

bits[0] = 0

for i = 1 .. n:
    bits[i] = bits[i & (i - 1)] + 1     // one more bit than i with its lowest 1 removed

That is dynamic programming with a one-line recurrence. bits[i >> 1] + (i & 1) works equally well and says the same thing differently: a number has the bits of its half, plus its own last one.

A related one-liner: x is a power of two exactly when it has a single set bit, so x > 0 and (x & (x - 1)) == 0. The x > 0 matters — without it, 0 passes.

Arithmetic by hand#

Add Binary is the odd one out on this list: it is not really a bit-trick problem, it is primary-school addition with two digits instead of ten. Walk both strings from the right, keep a carry, and do not stop until both strings and the carry are exhausted.

i = len(a) - 1
j = len(b) - 1
carry = 0
out = empty

while i >= 0 or j >= 0 or carry != 0:      // the carry can outlive both strings
    sum = carry
    if i >= 0: sum = sum + digit(a[i]); i = i - 1
    if j >= 0: sum = sum + digit(b[j]); j = j - 1

    append (sum % 2) to out
    carry = sum / 2

return reverse(out)

Two things account for nearly every failed submission. The loop condition must include carry != 0, or "1" + "1" returns "0". And the strings can be different lengths, so each index is guarded separately rather than assuming they run out together.

The temptation is to parse both strings to integers, add, and format back. Say why you are not doing it: the inputs can be longer than the language’s integer type, which is the whole reason the problem is phrased in strings.

What bites people#

The operators are simple; the type system underneath them is not.

• Signed right shift. In Java and C, >> on a negative number keeps the sign bit, so it never reaches zero — a while (x != 0) loop over the bits of -1 runs forever. Java’s >>> is the logical shift that fills with zeros; in C, do the counting on an unsigned type.
• Python integers are unbounded and conceptually infinite in two’s complement. ~5 is -6, and negative numbers have infinitely many leading 1s, so bit-counting loops need an explicit & 0xFFFFFFFF mask when a problem specifies 32-bit semantics.
• JavaScript coerces to 32-bit signed for every bitwise operator, so 1 << 31 is negative and anything above 2³¹ silently loses its high bits. >>> exists there too, and is the usual fix.
• Shifting too far is undefined in C and C++. 1 << 32 on a 32-bit int is not 0, it is undefined behaviour — and so is 1 << 31 on a signed int. Use 1u, or a wider type.
• Precedence is not what you expect. &, |, and ^ bind looser than == in C-family languages, so x & 1 == 0 parses as x & (1 == 0). Parenthesise.

Recognising it#

Reach for bit manipulation when:

• Values come in pairs, or in groups of k, and you want the odd one out. That is XOR almost every time.
• The problem talks about binary representation directly — counting bits, powers of two, binary strings.
• You need O(1) space where the natural solution is a set or a map, and the universe of values is small or self-cancelling.
• You are enumerating all subsets of a small collection — under about 20 items, a bitmask loop beats recursion for both speed and line count.
• A problem sets “without using + or -”, or a similar operator ban. That phrasing is always pointing at bitwise arithmetic.

And the counter-check: if none of those apply, bit tricks are usually the wrong tool. Clever bitwise code that saves nothing is harder to read and harder to defend in a review.

Summary#

Four identities carry most of the weight. x ^ x == 0 makes XOR an accumulator that forgets in pairs, which solves anything about odd occurrences in constant space. x & (x - 1) clears the lowest set bit, which turns counting into a loop over what is actually there. 1 << i builds a mask for a position, and by extension for a whole subset. Everything else on this page is one of those four applied to a specific question — plus the discipline of knowing what your language does to the sign bit.