That XOR Trick (2020)

Original Article ↗ Hacker News Discussion ↗

Algebraic properties and closed forms

  • Commenters formalize XOR using group theory: N‑bit integers with XOR form an Abelian group where each element is its own inverse; similar reasoning applies to addition with wraparound.
  • There’s a mini‑thread proving that inversion distributes over the group operation in an Abelian group, justifying identities like ~(x⋆y) = ~x⋆~y.
  • Several people point out the O(1) formula for xor(0..n): [n, 1, n+1, 0][n % 4], with explanations of the 4‑step cycle and bit‑level intuition.
  • Others generalize XOR as addition over GF(2) and discuss extending the “missing numbers” trick using finite fields and higher powers, connecting it to BCH and other error‑correcting codes.

Performance, loops, and overflow

  • Debate over doing two loops vs one: some argue micro‑optimizing loop counts and memory access patterns matters (cache, streams, tight loops); others say in Python the overhead is dominated by the interpreter and iterators, so structure matters less.
  • Discussion about using sum vs XOR: XOR avoids overflow because it’s “addition without carry”; others counter that with modular arithmetic (unsigned wraparound) even sum‑based approaches can be safe.
  • Multiple comments give closed‑form XOR(1..n) expressions to remove one of the loops entirely.

Interview question culture

  • Strong criticism of “xor trick” and similar puzzles as irrelevant trivia for most software jobs, likened to asking to rediscover nontrivial algorithms or theorems on the spot.
  • A contrasting view defends such questions as ways to see honesty (“I’ve seen this before”) and reasoning skills when the trick is unknown.
  • Several note it’s more appropriate for low‑level / systems roles than for typical web or business app development.

Classic XOR tricks, pitfalls, and uses

  • XOR swap is discussed, including the aliasing pitfall when swapping a[i] with itself, which can zero out data; this was famously abused in underhanded code.
  • XOR‑linked lists and “prev⊕next” storage get mentioned as clever but “evil” on modern CPUs.
  • Assembly angle: xor reg, reg as a compact, often fast way to zero registers on x86, though modern microarchitectures and other ISAs change the trade‑offs.
  • Real‑world uses cited: malware obfuscation, Redis HNSW graph integrity checks, Bitcoin’s minisketch, and Gray codes / Hamming distance.

Language‑specific and miscellaneous

  • Examples in J demonstrate the XOR‑missing‑number trick and the [n,1,n+1,0][n%4] pattern; there’s meta‑discussion about the tiny J community.
  • Some note pedagogical nits (e.g., truth‑table proof style, explaining XOR as inequality vs equality/XNOR) and alternative simple solutions (sums, bit arrays, sets, sorting).