Yinde's Blog

Talk is cheap. Show me the code.

目录
不用第三个 Temp 变量实现 两个变量之间交换的方法 {XOR 按位或异运算}
/      

不用第三个 Temp 变量实现 两个变量之间交换的方法 {XOR 按位或异运算}

相信平时大家应该经常会遇到需要交换两个变量值的情况,最常见的做法就是建立一个 temp 临时变量,用于交换,代码大概是这样。

// javascript
// swap
let a = 1 ,b = 2
let temp = a
a = b
b = temp

console.log(a) // 2
console.log(b) // 1

当然某些语言会提供更高级的解构语法实现变量的互换从而避免 temp 的建立,但显然不是每一种语言都拥有这样的语法糖。

事实如果借助位运算,我们可以在所有支持位运算的语言之中实现避免 temp 变量并实现变量互换。下面是一个典型示例

// javascript
// swap
let a = 1 ,b = 2

a = a ^ b
b = a ^ b
a = a ^ b

console.log(a) // 2
console.log(b) // 1

那么这背后的原理究竟是什么呢?

位运算

想要了解原理,我们必须深入计算机的内部,来研究一下布尔代数。

布尔代数拥有这些基本运算

  1. ~ NOT 非
  2. & AND 与
  3. | OR 或
  4. ^ XOR 按位异或

这里我们重点关注一下第四种,也就是我们使用的按位异或,他的计算规则如下

按位异或运算,对等长二进制模式或二进制数的每一位执行逻辑异或操作。操作的结果是如果某位不同则该位为1,否则该位为0。

举个例子:

[1,0,1] ^ [1,1,1] = [0,1,0]

XOR 运算拥有一个非常重要的特性: a ^ a = 0 , 这个特性类似整数运算中的 加法逆元 概念 ,在 XOR 运算中,一个元素的"加法逆元"就是其自身。无论参与运算的元素是单个布尔代数还是一个布尔代数组成的向量,都是成立的。也就是说 [1,1,1] ^ [1,1,1] = [0,0,0] 同时 1 ^ 1 = 0 ^ 0 = 0 。除此之外,我们还拥有一个特性,即 (a ^ b) ^ a = b,可以展开成 (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b。非常相似我们的整数加法,可以随意组合。

在了解到这些之后,我们就能对我们神奇的变量操作进行展开。见如下表格

步骤变量 a 的值变量 b 的值
初始ab
第一步a ^ ba
第二步a ^ b(a ^ b) ^ b
第三步(a ^ b ) ^ (a ^ b) ^ b(a ^ b) ^ b

我们只要按照上面两个核心特性进行化简即可

a = (a ^ b ) ^ (a ^ b) ^ b = (a ^ a) ^ (b ^ b) ^ b = 0 ^ 0 ^ b = b

b = (a ^ b) ^ b = (b ^ b) ^ a = 0 ^ a = a

就这样,我们得到了 a = b , b = a 的效果

参考

《CS:APP 深入了解计算机系统》


标题:不用第三个 Temp 变量实现 两个变量之间交换的方法 {XOR 按位或异运算}
作者:zhangzhengyi12
地址:https://blog.yinode.tech/articles/2019/10/31/1572505987718.html