XOR Tricks and Single Number

Why XOR Is Special

XOR earns its reputation because it behaves less like ordinary arithmetic and more like a perfect cancelation tool. Whenever two equal bits meet under XOR, the result is 0. Whenever two different bits meet, the result is 1. That means XOR answers the question “where do these two values differ?” at the bit level. In interview problems, that difference detector turns into something even more useful: a way to make duplicates disappear without sorting or extra memory.

The reason is algebraic. XOR is commutative, so the order does not matter. It is associative, so you can regroup values any way you like. And it is self-inverse, which means a ^ a = 0. Combine those three facts and any value that appears exactly twice cancels itself out, even if the duplicates are far apart in the array. What remains is the value whose partner never appeared. Once you see XOR as a cancelation operator instead of a weird symbol, the classic “single number” problems become almost inevitable.

Building the XOR Mental Model

A tiny truth table captures the whole operator. 0 ^ 0 = 0 and 1 ^ 1 = 0 because matching bits cancel. 0 ^ 1 = 1 and 1 ^ 0 = 1 because differing bits survive. Another way to say the same thing is that XOR tracks parity: a bit is 1 in the answer exactly when that position saw an odd number of 1s overall. If a position sees two 1s, or four 1s, or any even count, they pair off and disappear.

5  = 0101
5  = 0101
-----------
5^5= 0000

7 ^ 0 = 7
(2 ^ 9) ^ 2 = 9 because the two 2 values cancel each other

That parity view explains why XOR is a great fit for arrays where every value appears twice except one, or every value from 0 to n appears once except one. It also explains why XOR is not a magic hammer. If one number appears three times and another appears once, plain XOR does not separate them cleanly because an odd count of three still leaves one copy behind. The trick only works when the repetition pattern matches the algebra.

Worked Example: Single Number by Cancelation

Take the array [4, 1, 2, 1, 2]. A hash map would count frequencies, but XOR lets the duplicates erase themselves. Write the numbers in binary: 4 = 100, 1 = 001, 2 = 010. Now XOR from left to right. Start with 0 ^ 4 = 4. Then 4 ^ 1 = 101. Then 101 ^ 010 = 111, which is 7. XOR with the next 1 gives 110, which is 6. XOR with the final 2 gives 100, which is 4. The unmatched value is the only thing left standing.

Notice that the order looked chaotic in the middle. The running value jumped from 4 to 5 to 7 to 6 before returning to 4. That is normal. You do not need the intermediate states to be meaningful by themselves. The guarantee comes from the final regrouping argument: 4 ^ 1 ^ 2 ^ 1 ^ 2 can be rearranged as 4 ^ (1 ^ 1) ^ (2 ^ 2), which becomes 4 ^ 0 ^ 0, which is 4.

The missing-number variant uses the same idea in disguise. Suppose the array should contain every number from 0 through n, but one is absent. XOR all expected values and XOR all actual values. Every number present in both groups cancels out, so the missing value is the only one left. This is especially nice when you want O(1) extra space and you do not want to modify the array by sorting it.

expected: 0 ^ 1 ^ 2 ^ 3 ^ 4 = 4
actual:   3 ^ 0 ^ 1 ^ 4     = 6
answer:   4 ^ 6             = 2

Swapping Without a Temporary Variable

XOR can swap two values in place because information is never lost if you keep applying the same difference operation. If x and y start as distinct variables, doing x = x ^ y stores the bitwise difference. Then y = x ^ y recovers the old x, and x = x ^ y recovers the old y. This is a neat demonstration of self-inverse behavior, but in production code it is usually worse than a plain temporary variable because it is harder to read and easier to misuse.

The bigger interview lesson is not that XOR swap is clever. It is that algebraic identities let you move information around without auxiliary storage when the operation is reversible. XOR happens to be especially good at this because applying the same value twice undoes the first application. Once you internalize that idea, other XOR patterns become easier to spot. You start asking whether the problem is really about storing counts, or whether the input itself already contains a reversible bookkeeping structure.

Where Else XOR Shows Up

XOR also appears in error detection, parity checks, lightweight encryption demonstrations, and bitmask toggling. In graph and array problems, it often signals “difference between two sets” or “everything paired except one anomaly.” In low-level networking and storage systems, parity bits rely on the same odd-versus-even logic to detect or reconstruct data. So even if you first meet XOR in a coding interview, the idea has real engineering value beyond puzzle solving.

Another useful habit is to translate a problem statement into parity language. If an operation toggles membership, flips state, or says something happens an odd number of times, XOR is often nearby. If the prompt instead talks about exact multiplicities larger than two, sorted order, or arbitrary frequency counts, XOR alone is usually not enough. That simple diagnostic keeps you from both missing elegant XOR solutions and forcing XOR into problems where a map or sorting pass is the more honest tool.

Practice Problems

Quiz

Summary

• XOR keeps differences and cancels matches.
• a ^ a = 0 and a ^ 0 = a are the identities that power the classic tricks.
• Single Number and Missing Number both work because every matched value appears an even number of times in the combined XOR.
• Single Number III adds one extra idea: isolate a distinguishing set bit and partition the input.
• Understand the repetition pattern before reaching for XOR.