用XOR（异或）做数值交换

经常看到别人的代码，用3个XOR异或操作，就完成了数值交换，有点炫酷，本文记录一点关于这个骚操作的思考。

先上代码（C）：

void swap(int *a, int *b)
{
    *a ^= *b ^= *a ^= *b;
}

这段代码的执行顺序是从右到左的。先执行 *a ^= *b，然后 *b ^= *a，此时 *a 值已变，执行后 *b == 最初的 *a，最后执行 *a ^= *b，此时 *a == 最初的 *b。

代码写成这样，还是因为编译后执行速度更快！

有人这样解释XOR（异或）操作：a ^ b，从b的角度看，得到的结果是与a不一样的bit位全部为1，一样的bit位全为0，即做了一次bit位探测。如果此时对结果再做一次异或，a^b^b 就会等于 a。

看下面的测试（python）：

>>> 1^0^0
1
>>> 1^1^1
1
>>> 0^1^1
0
>>> 0^0^0
0
>>> 12^34^34
12
>>> 123^34^34
123
>>> 23^34^34
23

连续异或两个相同的值，结果回到原值！这就是用异或做交换的数学原理。

不过，上面的swap函数有一个“坑”！

有人说这是坑，我个人觉得应该不算。上面那个swap函数，如果传入的两个地址相同，就不再是swap了，而是清零。也许，本就不应该把同一个int（两个指向同一地址的指针）传入swap函数，逻辑上就有问题。

-- EOF --

相关文章

• 霍夫曼（Huffman）压缩编码算法
• 用位运算来判断数值的奇偶性
• KNN算法
• 用移位来进行乘除2的运算
• 7bit压缩编码
• 用移位和加法模拟计算机乘法
• 在MNIST和FMNIST数据集上测试KNN算法
• 用减法模拟计算机除法
• Shannon-Fano算法
• 哥伦布（Golomb）压缩编码