4.30.0 — Bit Manipulation: The Pattern

Recognition cue. The problem says "without extra memory", "appears once", "count the bits", "without using +", or the constraints mention 32-bit integers. Small subsets (n ≤ 20) also point here, via bitmasks.

The five operators, and what each is for

operator	does	use it to
&	1 only where both are 1	test a bit, clear bits
|	1 where either is 1	set a bit, merge two sets
^	1 where they differ	toggle a bit, cancel pairs
~	flips every bit	build a mask
<< >>	shift left / right	multiply or divide by 2, build a mask

Read them as set operations and they stop feeling like arithmetic: & is intersection, | is union, ^ is symmetric difference.

The four idioms worth memorising

x & (1 << i)          # is bit i set?
x |= (1 << i)         # set bit i
x &= ~(1 << i)        # clear bit i
x ^= (1 << i)         # toggle bit i

x & (x - 1)           # clear the LOWEST set bit
x & -x                # isolate the lowest set bit
x & 1                 # is x odd?
x >> 1                # x // 2  (for non-negative x)

x & (x - 1) is the one to understand rather than memorise. Subtracting 1 flips the lowest set bit to 0 and turns every 0 below it into 1. ANDing with the original keeps only the bits above, so the lowest set bit is gone.

x       = 1011 0100
x - 1   = 1011 0011      ← lowest 1 became 0, the zeros below became 1
x & (x-1) = 1011 0000    ← that bit cleared

Two consequences: counting set bits by looping until zero (Brian Kernighan's method), and testing for a power of two with x > 0 and x & (x - 1) == 0.

x & -x isolates it instead of clearing it, because -x is ~x + 1 in two's complement, which flips everything above the lowest set bit and leaves that bit alone. It is how Fenwick trees find their next index (4.13.4).

XOR: the three properties

XOR carries most of this chapter, and everything follows from three facts:

x \oplus x = 0 \qquad x \oplus 0 = x \qquad \text{XOR is commutative and associative}

So XOR-ing a list cancels every value that appears an even number of times, regardless of order. That single sentence solves Single Number, Missing Number, and finding a duplicate in a range.

XOR is also addition without carrying, which is why it appears inside Sum of Two Integers.

Bitmasks as sets

A subset of up to about 20 items fits in one integer, one bit per item.

for mask in range(1 << n):            # every subset of n items
    for i in range(n):
        if mask & (1 << i):           # is item i in this subset?
            ...

1 << n is 2^n. This is 4.18.1 Subsets done with integers, and it is the gateway to bitmask DP, where a subset becomes a DP state (4.29).

The language traps

Python integers are unbounded and negatives have infinitely many leading 1s. ~5 is -6, not a 32-bit pattern. To work in 32-bit arithmetic you must mask: x & 0xFFFFFFFF, and convert back to a signed value at the end. This is the single biggest source of confusion in Python bit problems, and 4.30.6 is where it bites.

JavaScript's bitwise operators coerce to 32-bit signed integers, even though numbers are otherwise doubles. So >> gives a signed shift and >>> gives an unsigned one — and using the wrong one on a value with the top bit set gives a negative result.

Java has >>> too, for the same reason. C and C++ leave shifting a signed negative value undefined. Know your language before claiming a bit trick is portable.

The seven problems

#	Problem	The one insight
4.30.1	Single Number ★	XOR cancels every pair
4.30.2	Number of 1 Bits ★	x & (x-1) clears the lowest set bit
4.30.3	Counting Bits ★	bits[i] = bits[i >> 1] + (i & 1)
4.30.4	Reverse Bits ★	Pull from the right, push to the left
4.30.5	Missing Number ★	XOR the indices with the values
4.30.6	Sum of Two Integers ★	XOR is the sum, AND-shifted is the carry
4.30.7	Reverse Integer	Check overflow before it happens

★ marks the Blind 75 subset.

What the interviewer will push on

"Explain x & (x-1)." Borrowing flips the lowest 1 and sets everything below it; the AND keeps only the bits above.

"Why does XOR solve this?" x ^ x = 0, and order does not matter.

"What does two's complement do to -x?" It is ~x + 1, which is why x & -x isolates the lowest set bit.

"Does this work in Python?" Only with masking — Python integers have no fixed width.

"How would you count set bits fastest?" x & (x-1) in a loop is O(\text{set bits}); a lookup table is O(1) per byte; and every modern CPU has a popcount instruction that the compiler will emit.

One thing to volunteer: read the operators as set operations. "& is intersection, | is union, ^ is symmetric difference." It makes bitmask problems obvious instead of cryptic.

Recall

• Read the operators as sets: & intersection, | union, ^ symmetric difference.
• XOR: x ^ x = 0, x ^ 0 = x, order does not matter. So XOR-ing a list cancels everything appearing an even number of times.
• x & (x-1) clears the lowest set bit — count bits with it, and test a power of two with x > 0 and x & (x-1) == 0.
• x & -x isolates the lowest set bit, because -x is ~x + 1.
• 1 << n is 2^n; iterate range(1 << n) to enumerate every subset of n items.
• Python integers are unbounded — mask with 0xFFFFFFFF to simulate 32 bits, and convert back to signed at the end.
• JavaScript bitwise operators coerce to 32-bit signed; use >>> for an unsigned shift.
• Check overflow before performing the operation, not after.

Next: 4.30.1 Single Number — the cleanest use of XOR there is.