HN Distilled

Essential insights from Hacker News discussions

That XOR Trick (2020)

Original Article

Hacker News Discussion

Here's a summary of the key themes from the Hacker News discussion:

The XOR Solution for Finding Missing Numbers

A central theme is the elegance and efficiency of using the XOR operation to find a single missing number in a sequence. This method leverages specific mathematical properties of XOR to achieve a fast solution.

  • "The trick works on any Abelian group. N-bit values form an Albanian group with xor where 0 is the identity and every element is its own inverse."
  • "The first thing that occurred to me is that if a number is missing from a list, the sum of that list will fall short. But I like XOR's."
  • "It really tickles my brain in a lovely way that it avoids all overflow risk as well"
  • "For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop."
  • "The author's solution is called the Hamming code: you set F(i) = i, and you do the additions by xoring."

Mathematical Properties and Proofs of XOR

The discussion delves into the mathematical underpinnings of why XOR works, particularly its properties within group theory and number theory. This includes discussions on closure, associativity, commutativity, and inversions.

  • "~Is there a simple proof for this type of identity?~"
  • "The trick works on any Abelian group."
  • "I believe you are implying: (g(1) ⋆ ... ⋆ g(n)) ⋆ ~(g(i(1)) ⋆ g(i(2)) ⋆ ... ⋆ g(i(n-1))) = g(m)"
  • "FBT: ... It does. For all x and y: ... (~x ⋆ ~y) ⋆ (x ⋆ y) = 0 (via associativity and commutativity)"
  • "hsfzxjy: To derive 'The XOR trick' I think both associativity and communitativity are needed."
  • "For those who do/did assembly, this is the common way to set a register to zero in x86 assembly (probably not only) because the instruction does not need an operand, so is shorter, and executes in one cycle only."

Performance and Implementation Details (Micro-optimizations vs. Big O)

A significant portion of the conversation revolves around the practical performance implications of different implementations. This includes debates about "O(2n)" vs. "O(n)", the cost of loops in Python, and the impact of caching and instruction sets.

  • "moron4hire: Why do people hate traditional for loops so much? In a conversation about petty micro optimizations, we end up performing two loops instead of one, all because sticking three operations in one statement is 'yucky'?"
  • "delifue: Its main benefit is to avoid having extra data structure (like hash map) to find the missing or duplicate, using O(n) time and O(1) space."
  • "moron4hire: No, again, that's not my point. The code from the article is O(2n) when it could be O(n). I know we're not supposed to care about constant factors, but I've lived in a world where not micro optimizing the ever loving shit out of my software could potentially make people throw up, so this sort of stuff kind of stands out to me."
  • "perfmode: real world performance will depend on how much of that N fits in cache. and in what cache it fits (L1, 2, 3). once loaded, you may not pay much cost to access each value a second time."
  • "MindSpunk: Doing 2 loops over the data means you have to do a full pass over the data twice. If your N doesn’t fit in L3 then you’re going to load N twice instead of once. Loading twice, even out of L1 is still slower than never loading twice at all."
  • "moron4hire: Even assuming python's foreach loop in these cases get optimized down to a very bare for loop, the operations being performed are dominated by the looping logic itself, because the loop body is so simple."
  • "sparkie: In long mode, compilers will typically emit xor eax, eax, as it only needs 2 bytes: The opcode and modrm byte."
  • "danbruc: Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four."

Technical Interview Questions - Relevance and Methodology

The discussion frequently touches upon the nature of technical interview questions, specifically whether this type of XOR problem is a good indicator of a candidate's skill or if it's merely trivia.

  • "ameliaquining: Ah, my least favorite technical interview question. (I've been asked it, but only after I first read about it online.)"
  • "motorest: > Ah, my least favorite technical interview question. The epitome of turning technical interviews into a trivia contest to make them feel smart."
  • "empiko: Is there any other field where they give you random brain teasers for an interview?"
  • "snozolli: It has no connection to modern software engineering. It's a clever and irrelevant trick for 99.999% of programming jobs out there."
  • "ur-whale: In what way is that question trivia? [...] Either you haven't and you can demonstrate to the interviewer your analytical skills by dissecting the problem step by step and understanding what the code actually does and how."
  • "anthomtb: Horses for courses. It's silly to as ask a web dev these questions and expect these XOR approaches."
  • "jonathanlydall: This was a go to interview question to be solved in C# at a place I worked at a while back which had developers allocated to projects working on pretty standard line of business systems."

Generalizations and Related Bitwise Operations

Several users expand on the XOR theme by discussing generalizations of the problem, how XOR relates to other bitwise operations, and more advanced applications.

  • "akovaski: The partitioning algorithm to find two missing/duplicate numbers is clever, I wouldn't have thought of that."
  • "mrbluecoat: PTSD for me on this topic due to a week wasted cleaning up PHP malware using XOR for obfuscation and encryption"
  • "XeO3: Apart from these applications of XOR, a favourite one is using Bitwise AND to find Even/Odd numbers."
  • "hundredwatt: A neat trick to make the accumulator both collision-resistant and self-diagnosing."
  • "less_less: Finding missing or extra numbers is closely related to error-correcting codes, especially binary linear codes."
  • "Straw: One can generalize this to k missing numbers the same way as we typically do for the addition case by using finite fields: XOR is equivalent to addition over the finite field F_2^m."