小技巧--使用异或来替换原本的常量交换

小技巧–使用异或来替换原本的常量交换

场景重现

我们在平时写代码的时候，倘若我们要交换a和b的值，是不是经常会用到下面这个代码？

int temp = a;
a = b;
b = temp;
1
2
3

这个算是十分基本的交换方法，被人津津乐道。

但，从优化的角度，有没有想过，不去使用temp这个变量呢？

那么，不用变量如何交换呢？

就要使用到我们今天的主角–异或运算了。

先打个结论，刚才那行代码是完全等于下面这些代码的：

a = a ^ b;
b = a ^ b;
a = a ^ b;
1
2
3

为什么呢？请听我娓娓道来。

先来说一下异或运算

异或运算就是一种对二进制的一种运算。相同得 0 ，不同得 1。例：

1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
1 ^ 1 = 0
1
2
3
4

如果是两个数的运算，就是：

4 ^ 5 =

4       0100
5       0101
       ------
        0001
1
2
3
4
5
6

又被称为不进位的相加。

同时又衍生出：

 n ^ n = 0
 n ^ 0 = n
1
2

同时异或满足结合律。

铺垫了这么多，该说一下为什么了。

我们把a的值设为 x , b的值设为 y。于是上面的变为：

a = a ^ b;  //此时a = x ^ y  b = y
b = a ^ b;  //此时a = x ^ y  b = x ^ y ^ y = x
a = a ^ b;  //此时a = x ^ y ^ x = y  b = x
1
2
3

你会惊讶的发现 a 和 b 调换完了。

这就是异或的魅力。

注意： 如果 a 和 b 指向的是同一个内存地址，那么这种方法就存在弊端，就会将原来的 a 和 b 都重置为0.

位运算详解以及有关的练习点击这里：“只出现一次的数字”系列 剑指offer–位运算学习(一)