Such tricks were maybe useful 40 years ago while writing assembly code manually or while using a dumb compiler with no optimizations. But nowadays such tricks are near to useless. All useful ones (like optimizing division by 2 via bitshift ) are already implemented as compiler optimizations. Others shouldn't be used in order to avoid making optimizer's job harder.
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.
Xor swap trick has perfect profile for underhanded C contests. It generally works until a specific condition triggers its failure. The condition is "the arguments are aliases", so for example XOR_SWAP(a[i], a[j]) when i=j.
You can use this same property of xor to make a double-linked list using just one pointer per item, which is xor of the previous and next item addresses!
It still is. The CPU's register renamer can detect these instructions to not have data dependencies and can zero the register itself. It doesn't send the instruction to the execution engine meaning they use no execution resources and have zero latency.
> given a list where every value appears exactly twice except one, XOR all the values together and the duplicates cancel out, leaving the unique element
For some reason this reminds me of the Fourier transform. I wonder if it can be performed with XOR tricks and no complicated arithmetic?
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.
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.
Such tricks were maybe useful 40 years ago while writing assembly code manually or while using a dumb compiler with no optimizations. But nowadays such tricks are near to useless. All useful ones (like optimizing division by 2 via bitshift ) are already implemented as compiler optimizations. Others shouldn't be used in order to avoid making optimizer's job harder.
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
`xor eax, eax` is less code when assembled. That's why compilers generate it.
..and reliably generate it for decades, but you can still manually do it in C for bonus stylistic points!
>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).
Modern compilers will still use xor for zeroing registers on their own.
For instance: https://godbolt.org/z/n5n35xjqx
Variable a(register esi) is first initialized to 42 with mov and then cleared to zero using xor.
Yes, the whole comment is tongue in cheek for pointless manual optimizations.
Xor swap trick has perfect profile for underhanded C contests. It generally works until a specific condition triggers its failure. The condition is "the arguments are aliases", so for example XOR_SWAP(a[i], a[j]) when i=j.
xor swap trick was useful in older simd (sse1/sse2) when based on some condition you want to swap values or not:
If mask = 0xfff...fff then a/b will be swapped, otherwise if mask = 0 then they'll remain the same.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.
You can use this same property of xor to make a double-linked list using just one pointer per item, which is xor of the previous and next item addresses!
Except such "optimization" may affect performance on CPUs with speculative execution/prediction. But it should be measured.
30 years ago, when I wanted to 0 a register in assembly I used something like xor ah, ah because it was a bit more performant.
It still is. The CPU's register renamer can detect these instructions to not have data dependencies and can zero the register itself. It doesn't send the instruction to the execution engine meaning they use no execution resources and have zero latency.
> given a list where every value appears exactly twice except one, XOR all the values together and the duplicates cancel out, leaving the unique element
For some reason this reminds me of the Fourier transform. I wonder if it can be performed with XOR tricks and no complicated arithmetic?
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.
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.