Bit manipulation — XOR tricks, LSB, counting set bits: Worked examples

The scenario matrix

Before any example, let's list every cell a bit-trick problem can land in. Read this like a checklist — each worked example carries a tag telling you which cell it fills.

Cell	Case class	What makes it tricky	Filled by
A	XOR, all-pairs-except-one	pairs must be even count	Ex 1
B	XOR, two unique numbers	one XOR pass isn't enough	Ex 2
C	XOR on the degenerate input (empty / single)	limiting behaviour	Ex 3
D	`x & -x` on a positive number	isolate lowest set bit	Ex 4
E	`x & -x` on zero and on a negative (two's complement)	sign / degenerate	Ex 5
F	`x & (x-1)` power-of-two test, incl. `x=0`	the false-positive trap	Ex 6
G	popcount, dense vs sparse	which loop wins	Ex 7
H	word problem (real world)	translating words to bits	Ex 8
I	exam twist: "everything thrice except one"	XOR fails, need mod-3	Ex 9

Every symbol used below was defined in the parent: $\oplus$ is XOR (bit is 1 when the two bits differ), $b_{i}$ is the bit at place value $2^{i}$ , and the LSB is bit $0$ (the rightmost switch).

Ex 1 — Cell A: the classic "single number"

Ex 2 — Cell B: TWO numbers appear once (the two-loner twist)

Worked example Every number appears twice except

two distinct numbers. Find both. Array [2, 4, 7, 4, 2, 9] — loners are 7 and 9.

Forecast: one XOR pass gives you $7 \oplus 9$ , not the two numbers. How do you split them apart?

XOR the whole array → x = 7 ^ 9. Why this step? pairs cancel, so x is the XOR of only the two loners: $7 \oplus 9 = 0111 \oplus 1001 = 1110 = 14$ .
x is non-zero, so the two loners differ in at least one bit. Grab any set bit of x with the LSB trick: $mask = x & - x = 14 & - 14 = 2$ Why this step? a set bit in x marks a position where the two loners disagree (that's what XOR being 1 means). We use that position as a splitter.
Partition the array by that bit. Numbers with bit-1 set go in group X, others in group Y. XOR each group separately. Why this step? every duplicate pair lands in the same group (identical numbers share all bits), so it still cancels. The two loners land in different groups (they disagree at mask). Each group now reduces to a single loner — Cell A twice.
- Group with bit 2 set: 2, 7, 2 → 2^7^2 = 7.
- Group without: 4, 4, 9 → 4^4^9 = 9.
Answers: 7 and 9.

Verify: 7 ^ 9 = 14, 14 & -14 = 2, and the two groups XOR to 7 and 9. ✓

Ex 3 — Cell C: degenerate inputs (empty and single-element)

Ex 4 — Cell D: `x & -x` on a positive number

Worked example Isolate the lowest set bit of

x = 20. $20 = 1010 0_{2}$ .

Forecast: which power of two comes out — the $2^{4}$ (the top set bit) or the $2^{2}$ (the low one)?

Write the bits. $20 = 10100$ . The lowest 1 sits at position $k = 2$ (place value $2^{2} = 4$ ). Why this step? the trick's whole job is to find that position.
Form -20 in two's complement: flip all bits of 00010100 → 11101011, then add 1 → 11101100. Why this step? the parent showed $- x = \neg x + 1$ ; the "+1" ripples up through the trailing zeros and stops exactly at bit $k$ , re-creating a 1 there.
AND them (look at the figure's aligned rows): $00010100 & 11101100 = 00000100 = 4$ Why this step? above bit $k$ the two rows are complements → all zero; at bit $k$ both are 1 → survives; below bit $k$ both are 0.
Answer $= 4 = 2^{2}$ — the lowest set bit, not the highest.

Verify: 20 & -20 = 4. ✓

Ex 5 — Cell E: `x & -x` on zero and on a negative

Worked example Evaluate

x & -x for x = 0 and for x = -12.

Forecast: zero has no set bit — what can the trick possibly return? And does it even make sense for a negative number?

Zero. -0 = 0, so 0 & 0 = 0. Why this step? there is no lowest set bit; the trick correctly returns 0 (its "nothing found" signal). Always guard x != 0 before using the result as a real bit.
Negative, -12. In 8-bit two's complement $- 12 = 11110100$ . Why this step? the trick is defined on the bit pattern, and two's complement gives every negative a concrete bit row.
-(-12) = 12 = 00001100. AND with 11110100: $11110100 & 00001100 = 00000100 = 4$ Why this step? the identity x & -x still isolates the lowest set bit of the stored pattern; the lowest 1 of -12's pattern is at position 2.
Answers: 0 & -0 = 0, and -12 & 12 = 4.

Verify: 0 & 0 = 0; and for -12, (-12) & (-(-12)) = (-12) & 12 = 4. ✓

Ex 6 — Cell F: power-of-two test, and the `x = 0` trap

Worked example Classify each with

x & (x-1) == 0: 16, 18, 0.

Forecast: which of these three passes the naive (x & (x-1)) == 0 test — and which one fools it?

16 = 10000. x-1 = 15 = 01111. AND → 00000 = 0. Power of two ✓ (exactly one set bit; dropping it gives 0). Why this step? subtracting 1 flips the lone 1 to 0 and the zeros below to 1s; AND with the original clears the whole thing.
18 = 10010. x-1 = 17 = 10001. AND → 10000 = 16 ≠ 0. Not a power of two. Why this step? 18 has two set bits; dropping the lowest still leaves 16, so the test is non-zero.
0. x-1 = -1 = …11111 (all ones in two's complement). 0 & -1 = 0. Why this step? here's the trap: 0 passes (x & (x-1)) == 0 but is not a power of two. So the correct test needs an extra guard: x != 0 && (x & (x-1)) == 0.
Verdicts: 16 ✓, 18 ✗, 0 ✗ (needs the guard).

Verify: 16 & 15 == 0 (true); 18 & 17 == 16 (non-zero); 0 & -1 == 0 but the guarded test 0 != 0 is false. ✓

Ex 7 — Cell G: popcount, sparse vs dense

Ex 8 — Cell H: real-world word problem

Worked example A parking-garage sensor logs each car's slot ID every time it enters

and every time it leaves. At day's end one car is still inside (logged an odd number of times); all others are paired (in+out). Slot IDs logged: [13, 8, 13, 8, 8, 8, 21]. Which car is still parked?

Forecast: which slot appears an odd number of times? Eyeball it, then let XOR confirm.

Model each log as a bit-vector value; XOR the whole log stream. Why this step? an entry+exit pair is the same slot ID twice → self-inverse cancels it. A car still inside has an odd log count → survives. This is exactly Cell A dressed as a story.
Fold: 13^8^13^8^8^8^21. Regroup: (13^13) ^ (8^8^8^8) ^ 21 = 0 ^ 0 ^ 21. Why this step? 13 appears twice (even → 0); 8 appears four times (even → 0); 21 appears once (odd → survives).
Answer: slot 21 is still parked.

Verify: 13^8^13^8^8^8^21 == 21, and 21 is the only odd-count ID. ✓

Ex 9 — Cell I: exam twist — XOR fails here

Worked example Every number appears

three times except one, which appears once. Find it. Array [6, 6, 6, 4].

Forecast: will plain XOR give the answer? Try it first: 6^6^6^4 = ?

Show XOR breaks. 6^6^6^4 = (6^6)^6^4 = 0^6^4 = 6^4 = 2. That is not the answer (answer should be 4). Why this step? XOR cancels in pairs (mod 2). Three copies of 6 leave one 6 uncancelled, corrupting the result. So XOR only works when everything-else is even.
The right tool: count each bit position mod 3. For each of the (say) 8 bit positions, add up how many array numbers have a 1 there, then take that sum mod 3. Why this step? a number appearing three times contributes 3 (or 0) to each position → vanishes mod 3. The loner contributes 1 at exactly its own set bits, which survive mod 3.
Position 2 (value 4): numbers with bit 2 set are 6,6,6 (each 110) plus 4 (100) → count 4; 4 mod 3 = 1 → keep. Position 1 (value 2): 6,6,6 have it, 4 doesn't → count 3; 3 mod 3 = 0 → drop. Why this step? rebuilding the answer bit-by-bit from the surviving positions.
Surviving bits: only position 2 → answer = 4.

Verify: naive 6^6^6^4 == 2 (wrong), while the per-bit mod-3 reconstruction gives 4, matching the true loner. ✓

Recall Which cell is my problem?

Everything even except one loner? ::: Cell A — single XOR fold. Two loners? ::: Cell B — XOR all, split on one differing bit with x & -x, XOR two groups. Need the lowest set bit / a splitter mask? ::: x & -x (guard against x == 0). Is x a power of two? ::: x != 0 && (x & (x-1)) == 0 — never forget the x != 0 guard. Everything appears three (odd, >2) times except one? ::: XOR fails — count bits mod 3.

Connections

Two's Complement Representation — makes Ex 5's negative x & -x concrete.
Hash Sets vs O(1)-space tricks — every example here trades a hash set for $O (1)$ space.
Bitmask Dynamic Programming — Ex 8's "value as a set of bits" idea generalises.
Logarithms and Powers of Two — Ex 6's power-of-two structure.
Greedy and Divide-and-Conquer — Ex 2's split-into-two-groups is divide-and-conquer.
← Back to parent topic