异或交换算法中的小坑

突然想起来挺久前的一件事，因为太琐碎就不放到「深夜学算法」系列里了。

「交换两数」大概是编程入门者紧接着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

1. 经过 x ^= y
   x = 00000110，y = 00000101
2. 经过y ^= x
   x = 00000110，y = 00000011
3. 经过x ^= y
   x = 00000101，y = 00000011

此时x = 5，y = 3，交换成功。

看起来非常漂亮，但用C/C++实现时，有一个隐藏的小坑。

---

知道这个交换算法时我正在练习各种排序算法，就直接用在快速排序里了。写完代码一运行，别说排好序了简直比随机数还随机数。

当然作为C/C++学习者，我的第一反应是：

又搞错指针了耶…

但对着教材看了几遍快速排序的实现都没找到错误，用特殊输入试了几次后，我突然发现了问题所在。

交换两数有一个特例：「要交换的两个数指向同一片存储区域」。

什么意思呢？就是说可能会调用swap(x, x)，这件事虽然很傻，但调用后应该保证x的值不变。然而上面实现的xor_swap就在这里出了问题。

还是假设x = 3，写成二进制就是00000011：

1. 经过x ^= y
   x = 00000000
2. 经过y ^= x
   x = 00000000
3. 经过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;
    }
}

这件事情的启示有两条：

1. 遇事不决，先看wiki
2. 数学算法和程序实现还是有差别的