算法数据结构奇技淫巧3：交换两个数

3、交换两个数

交换两个数相信很多人天天写过，我也相信你每次都会使用一个额外来变量来辅助交换，例如，我们要交换 x 与 y 值，传统代码如下：

int tmp = x;
x = y;
y = tmp;

这样写有问题吗？没问题，通俗易懂，万一哪天有人要为难你，不允许你使用额外的辅助变量来完成交换呢？你还别说，有人面试确实被问过，这个时候，位运算装逼大法就来了。代码如下：

x = x ^ y   // （1）
y = x ^ y   // （2）
x = x ^ y   // （3）

我靠，牛逼！三个都是 x ^ y，就莫名交换成功了。在此我解释下吧，我们知道，两个相同的数异或之后结果会等于 0，即 n ^ n = 0。并且任何数与 0 异或等于它本身，即 n ^ 0 = n。所以，解释如下：

把（1）中的 x 带入 （2）中的 x，有

y = x^y = (x^y)^y = x^(y^y) = x^0 = x。 x 的值成功赋给了 y。

对于（3）,推导如下：

x = x^y = (x^y)^x = (x^x)^y = 0^y = y。

这里解释一下，异或运算支持运算的交换律和结合律哦。

怎么样？有木觉得很多牛逼？