Discussion

Too much Discussion of the XOR swap trick

ranger_danger: > given a list where every value appears exactly twice except one, XOR all the values together and the duplicates cancel out, leaving the unique elementFor some reason this reminds me of the Fourier transform. I wonder if it can be performed with XOR tricks and no complicated arithmetic?

mmozeiko: xor swap trick was useful in older simd (sse2) when based on some condition you want to swap values or not: tmp = a ^ b a ^= tmp & mask b ^= tmp & mask If mask = 0xfff...fff then a/b will be swapped, otherwise if mask = 0 then they'll remain the same.

CJefferson: Oh, that is cool, I’ve never seen that. I might add that to an extended version of the post sometime, I’ll be sure to credit you.

gobdovan: The XOR trick is only cool in its undefined-behavior form:a^=b^=a^=b;Which allegedly saves you 0.5 seconds of typing in competitive programming competitions from 20 years ago and is known to work reliably (on MinGW under Windows XP).Bonus authenticity: use `a^=a` to zero a register in a single x86 instruction (and makes a real difference for compiler toolchains 30+ years old).For real now, a very useful application of XOR is its relation to the Nim game [0], which comes in very handy if you need to save your village from an ancient disgruntled Chinese emperor.[0] https://en.wikipedia.org/wiki/Nim

fluoridation: There's a more general formulation, which is that every value but one must appear even numbers of times, and the one must appear some odd number of times.

twiceaday: How about every value appears 0 mod n times except one which appears 1 mod n times? :)Solution: xor is just addition mod 2. Write the numbers in base n and do digit-wise addition mod n (ie without carry). Very intuitive way to see the xor trick.