Every value in an array appears twice except one. Find it, and tell me when bit tricks are worth reaching for

Three identities, then the fold

XOR has exactly the properties needed. Any value XORed with itself is zero, any value XORed with zero is unchanged, and the operation is both commutative and associative. Put those together and folding XOR over the whole array is order-independent, every pair annihilates wherever the two copies sit, and what survives is the value with no partner.

int single = 0;
for (int x : nums) single ^= x;   // pairs cancel; associativity means position never matters
return single;

O(n) time, O(1) space, one pass. Now say the precondition out loud, because it is doing more work than the code: exactly one value appears once and every other appears exactly twice. Feed it a value appearing three times and it returns a wrong answer with no signal at all. The general statement is that the fold yields the XOR of everything appearing an odd number of times, which is only the answer you want when precisely one value qualifies.

Extending it to two unpaired values

Fold everything and you get a ^ b, which is non-zero because a != b. Every set bit in that result is a position where a and b disagree, so picking any one of them splits the array into two groups, each containing exactly one of the unpaired values and both copies of every paired value. Isolating the lowest such bit is the two's-complement identity x & -x, which works because negation is bitwise complement plus one, leaving only the lowest set bit in agreement.

int total = 0;
for (int x : nums) total ^= x;                    // total == a ^ b
int bit = total & -total;                         // lowest position where a and b differ

int a = 0;
for (int x : nums) if ((x & bit) != 0) a ^= x;    // duplicates always land in the same partition
return new int[] { a, a ^ total };                // recover b without a second pass

This one is a genuine extension rather than a second trick, since it reuses the same fold twice with a partition in between.

Where XOR runs out

Change the multiplicity to three and XOR gives you nothing usable, which is worth volunteering because it shows the limit is understood rather than papered over. The working approach counts bits positionally: for each of the 32 bit positions, sum that bit across every value and take the sum modulo 3, since the tripled values contribute multiples of 3 and only the unique value leaves a remainder. That is O(32n) time and O(1) space, and it is a different idea, not a variation.

Masks as sets, which is the part that pays

The reason bit manipulation is on the syllabus at all is not the puzzles. It is that a machine word is a set over a small universe, with every set operation costing a single instruction. Bit i set means element i is present; union is |, intersection is &, difference is & ~, membership is (m >>> i) & 1, and cardinality is Integer.bitCount(m). Iterating all subsets of an n-element universe is for (int m = 0; m < (1 << n); m++).

Two idioms carry most of the value. Iterating the submasks of a mask is for (int s = m; s > 0; s = (s - 1) & m), with the empty submask handled outside the loop; summed over every mask that is 3^n rather than 4^n total work, because each bit independently sits in s, in m without s, or outside m entirely. And bitmask dynamic programming turns "which subset have I already used" into an array index, which is what makes the Held-Karp formulation of the travelling salesman problem O(2^n · n²) time and O(2^n · n) space instead of factorial — tractable to roughly twenty cities on ordinary hardware.

That is a technique, and it shows up in real code: permission and capability flags, bitset intersection of posting lists in a search index, free-block maps in allocators, occupancy boards in chess engines.

The pitfalls that bite in the language, not the algorithm

Java masks a shift count to the low five bits for int, so 1 << 32 is 1 and not 0, and 1 << 31 is negative. Use 1L << k once k can reach 31. >> sign-extends while >>> does not, so peeling bits off a possibly-negative value with >> never terminates. In C and C++, shifting by at least the type's width is undefined behaviour rather than a defined wraparound. In Python integers are arbitrary precision, so any 32-bit reasoning needs an explicit & 0xFFFFFFFF and a manual sign fix-up.

Which of these earns its place

Be straight about the single-number fold: a HashSet solves the same problem in O(n) time and O(n) space, generalises to any multiplicity by counting, and reads correctly to anyone. The XOR version wins only when constant space is a stated constraint, and in a code review you would ask for a comment on it, because a reader has no way to recover the invariant from the code. Presenting it as the obviously superior solution is the answer that gets marked down, since it suggests the trade-off was never seen.

Masks-as-sets is the opposite. It changes what is computable rather than what is compact, and no readable alternative gives you 2^n states as an array index or set intersection in one instruction. When an interviewer asks whether bit manipulation matters, that distinction is the answer: one of these is a memorised identity with a fragile precondition, and one is how you make exponential state spaces fit in memory.

Reach for XOR when constant space is required and say what the fold assumes; reach for masks when a subset needs to be an index. Treating both as the same skill is what makes bit manipulation look like trivia.