Bits: XOR, Masks & the n&(n-1) Trick

Integers are arrays of bits

Every integer is stored as 32 (or 64) binary digits — bits. The number 13 is 1101: one 8, one 4, no 2, one 1. Bit manipulation means operating on those digits directly, with operators that touch all 32 bits in a single CPU instruction. Five operators cover everything:

Left-shifting by k multiplies by 2^k; right-shifting divides. From these, three idioms you should be able to write cold:

(x >> k) & 1      # test bit k: is it set?
x | (1 << k)      # set bit k to 1
x & ~(1 << k)     # clear bit k to 0

A pattern of bits used this way — as a bundle of on/off flags — is called a mask.

XOR's superpower: pairs cancel

Two identities make XOR the star of this module: x ^ x = 0 (a number cancels itself) and x ^ 0 = x (zero is invisible). Add that XOR is commutative and associative — order never matters — and you get: XOR everything together, and anything appearing an even number of times vanishes.

Single Number hands you an array where every element appears twice except one. XOR the whole array; the pairs annihilate; the loner remains:

acc = 0
for v in nums:
    acc ^= v
return acc

For [4, 1, 2, 1, 2]: the 1s cancel, the 2s cancel, 4 survives. O(n) time, O(1) space, no hash set.

Missing Number — the array holds n distinct numbers from 0..n, one missing — is the same trick in disguise: XOR all the indices 0..n together with all the values. Every present number appears twice (once as index, once as value) and cancels; the missing one appears once, as an index only, and survives. Two alternatives worth naming in an interview: the Gauss sum — expected total n(n+1)/2 minus the actual sum — and cyclic sort, swapping each value toward index home and scanning for the mismatch. All three are O(n)/O(1); offering a second one shows range.

n & (n-1): snap off the lowest set bit

The expression n & (n - 1) clears the lowest set bit of n, and nothing else. Why: subtracting 1 flips the lowest 1 to 0 and all the zeros below it to 1s (10100 - 1 = 10011); ANDing with the original wipes exactly that region while leaving every higher bit alone.

Two immediate payoffs:

Counting set bits (popcount) — loop until zero, one iteration per set bit rather than per bit position:

count = 0
while n:
    n &= n - 1   # one set bit disappears per loop
    count += 1

Power-of-two test — a power of two has exactly one set bit, so n > 0 and n & (n - 1) == 0.

A cousin worth knowing: x & (-x) isolates the lowest set bit (returns just that bit, rather than removing it).

Counting Bits: a one-line DP over binary structure

Counting Bits asks for the popcount of every number 0..n. Doing the Kernighan loop n times is O(n log n) — fine, but there is an O(n) recurrence hiding in the binary representations: shifting right by one drops the last bit, so

bits[i] = bits[i >> 1] + (i & 1)

— the count for i is the count for i-without-its-last-bit, plus that last bit. The table for 0..8: 0, 1, 1, 2, 1, 2, 2, 3, 1. Each entry reads an already-computed smaller entry: bit manipulation and DP shaking hands.

Reverse Bits: rebuild from the other end

Reversing the 32 bits of an integer is a mechanical pump: 32 times, pull the lowest bit off the input and push it onto the result from the right:

result = 0
for _ in range(32):
    result = (result << 1) | (n & 1)
    n >>= 1

Nothing clever — the exercise is keeping the two shift directions straight.

Addition without +: XOR is a half-adder

Adding two binary numbers by hand, each column produces a sum bit and a carry. Those two outputs are bitwise operators: XOR is addition ignoring carries, and AND, shifted left one, is exactly the carries. Loop until the carry runs dry:

while b != 0:
    carry = (a & b) << 1
    a = a ^ b        # carry-free sum
    b = carry        # carries to apply next round
return a

Trace 5 + 3 (101 + 011): XOR gives 110, carry gives 010. Next round: 110 ^ 010 = 100, carry 100. Next: 100 ^ 100 = 000, carry 1000. Next: 0 ^ 1000 = 1000 = 8, carry 0. Done. Each round pushes carries one bit left, so at most 32 rounds.

The Python caveat: Python integers are unbounded, so a negative number's two's-complement bits never terminate and the loop can spin forever. Simulate 32-bit behavior by masking: keep a & 0xFFFFFFFF each round, and at the end, if the result's bit 31 is set, convert back to a negative Python int (~(a ^ 0xFFFFFFFF)). In Java or C++, the fixed-width types make the plain loop just work.

The pitfalls that actually bite

• Operator precedence: bitwise operators bind looser than comparisons. x & 1 == 0 parses as x & (1 == 0) — always parenthesize: (x & 1) == 0.
• Arithmetic vs logical right shift: on negative numbers, some languages copy the sign bit in (>> in Java), others provide a zero-filling variant (>>>). Know which your language does before shifting negatives.
• 32-bit limits: signed 32-bit ints span -2^31 to 2^31 - 1. Problems like Reverse Integer make the overflow check the whole point — check before appending the next digit, not after.
• ^ is XOR, not exponentiation — a classic silent bug for anyone arriving from math notation.

Recognition signals

Reach for bits when you see: "every element appears twice except…" (XOR fold), "without using + or -" (half-adder loop), "count the 1 bits" (n & (n-1)), "power of two", "O(1) extra space" on a pairing or missing-element problem, or subsets over n ≤ 20 items (encode each subset as a mask). The vocabulary is small; the wins are outsized.