Too much discussion of the XOR swap trick
3 days ago
- #bitwise-operators
- #compiler-optimization
- #xor-swap-trick
- 异或交换技巧是一种无需临时变量交换两个变量的方法，它利用了异或的自反性，即 a ^ a == 0 和 a ^ 0 == a。
- 编译器通常会优化掉异或交换，为局部变量生成与临时变量交换相同的代码；对于指针，由于别名问题，异或交换效率较低，除非使用 restrict 关键字。
- 异或交换技巧主要是一种趣味性的方法，在寄存器用尽等有限场景（如汇编语言）中有用，但在 x86 等具有专用交换指令的架构上已过时。
- 其他异或技巧包括在一个所有其他元素都出现两次的列表中寻找唯一元素，利用异或在 O(n) 时间和 O(1) 空间内消除重复项。