突然想起来挺久前的一件事，因为太琐碎就不放到「深夜学算法」系列里了。
「交换两数」大概是编程入门者紧接着Hello World写的程序，常用和知名到都有段子：
// 普通程序员
void normal_swap(int &x, int &y) {
int temp = x;
x = y;
y = temp;
}
// 二逼程序员
void foolish_swap(int x, int y) {
int temp = x;
x = y;
y = temp;
}
通常交换两数都会使用临时变量temp，但是也有不使用的方法，称为异或交换算法（XOR swap algorithm）：
void xor_swap(int &x, int &y) {
x ^= y;
y ^= x;
x ^= y;
}
算法本身算是广为人知，原理也很简单。假设x = 3，y = 5，那么分别写成二进制形式就是x = 00000011，y = 00000101
- 经过 x ^= y
x = 00000110，y = 00000101 - 经过y ^= x
x = 00000110，y = 00000011 - 经过x ^= y
x = 00000101，y = 00000011
此时x = 5，y = 3，交换成功。
看起来非常漂亮，但用C/C++实现时，有一个隐藏的小坑。
知道这个交换算法时我正在练习各种排序算法，就直接用在快速排序里了。写完代码一运行，别说排好序了简直比随机数还随机数。
当然作为C/C++学习者，我的第一反应是：
又搞错指针了耶…
但对着教材看了几遍快速排序的实现都没找到错误，用特殊输入试了几次后，我突然发现了问题所在。
交换两数有一个特例：「要交换的两个数指向同一片存储区域」。
什么意思呢？就是说可能会调用swap(x, x)，这件事虽然很傻，但调用后应该保证x的值不变。然而上面实现的xor_swap就在这里出了问题。
还是假设x = 3，写成二进制就是00000011：
- 经过x ^= y
x = 00000000 - 经过y ^= x
x = 00000000 - 经过x ^= y
x = 00000000
所以无论x原来的值是什么，调用swap(x, x)后都变成0了。
好一个すべてがゼロになる（全部成为0）！
解决起来很简单，判断一下两个数是否相等，相等不用交换，不相等肯定不指向同一片存储区域。
所以正确的异或交换算法实现应该是：
void xor_swap(int &x, int &y) {
if(x != y) {
x ^= y;
y ^= x;
x ^= y;
}
}
这件事情的启示有两条：
- 遇事不决，先看wiki
- 数学算法和程序实现还是有差别的
