0

I've been looking into how to use the XOR operator to solve some classic problems like finding the missing number in a sequence. I understand how XOR achieves this by cancelling out duplicates through its properties (e.g. commutativity, x ^ x = 0, x ^ 0 = x, etc.)

What I don't understand is this alternative approach in this question which says that:

(PARTIAL SUM) XOR (MISSING ELEMENT) = (TOTAL)

Why is this the case? And does it always work? I did it with pen and paper testing it on sequences of 3's starting from 0 (i.e. [00, 01, 10] then [01, 10, 11], etc...) and noticed that this works but breaks down at the sequence [2, 3, 4] if we take 3 to be the missing number: (2+4) ^ 3 = 5 instead of the actual total 9.

On another note, that same answer states that:

A XOR B = C => C XOR A = B

What's the logic behind this equivalence?

Metrician
  • 153
  • 1
  • 1
  • 10
  • 2
    In this case the "partial sum" and "total" are really "partial xor" and "total xor"; not "partial addition" and "total addition". That "(partial xor) XOR (missing value) = (total xor)" is just the definition of "partial xor" and "total xor". – Raymond Chen Dec 16 '21 at 14:30
  • Thank you for this clarification. Now it makes much more sense – Metrician Dec 21 '21 at 15:13

0 Answers0