Fork me on GitHub

三次异或运算交换两值问题

发表于 | 更新于 | 本文总计 493 字

 最近在看位运算的一些东西，发现很多操作还是很有意思的。

为什么三次异或操作能够交换两值（整数）

背景

1
2
3
4
5
6
7
a = 11;
b = 5;
a = a ^ b;
b = a ^ b;
a = a ^ b;
a; // 11
b; // 5

原理

  任何功能的实现都是依赖于“算法”的，而算法的出现归根到底来自于生活和数理规律的总结。

  位运算实际上是转为二进制进行运算的，那两个值的差异无非就是不同位上0与1的差别，要交换两个值就是把相同位上的不同值互换了，对于位数不同的值，补0即可。

例子

  交换11和5，11的2进制表示是1011，5的2进制表示是101，补0就是0101。我们知道^操作，是只有当两个操作数不同时才返回1，其余情况返回0；利用该特性，我们先令a = 11，b = 5，第一次11与5进行^操作，可以得到a = a ^ b => 1110，再对b = a ^ b => 1011，最后回到a = a ^ b => 0101。此时已然完成交换。

结论

  通过观察这个过程我们可以得到一个什么结论呢？即(a ^ b ^ b) === a以及(a ^ b ^ a) === b，为什么有3次异或，是因为要保存第一步的异或结果，然后在第二步中，让b运算拿到a的值，第三步等价于(a ^ b ^ a ^ b ^ b) === b转换一下就是(b ^ b ^ b) === b，再转换就是(b ^ 0) === b，最终a拿回b的值。