Too much discussion of the XOR swap trick
a day ago
- #bitwise-operators
- #compiler-optimization
- #xor-swap-trick
- The XOR swap trick is a method to swap two variables without a temporary variable, using XOR's self-inverse property where a ^ a == 0 and a ^ 0 == a.
- Compilers often optimize XOR swaps away, producing identical code to temporary variable swaps for local variables, and with pointers, XOR swaps are less efficient due to aliasing issues unless restrict is used.
- The XOR swap trick is mostly a curiosity, useful in limited scenarios like assembly when out of registers, but obsolete on architectures like x86 with dedicated exchange instructions.
- Other XOR tricks include finding a unique element in a list where all others appear twice, using XOR to cancel duplicates in O(n) time and O(1) space.