异或运算的妙用
2023-02-01 算法
概述
异或运算 通过对两个相同长度的二进制数进行逐位比较，若对应位的值不同，结果为 1, 否则结果为 0, Go 语言中使用的运算符号为 ^。
下面举几个简单的小例子:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
运算定律
交换律
x ^ y = y ^ x
结合律
x ^ (y ^ z) = (x ^ y) ^ z
任何数与自身进行异或运算，结果都为 0
x ^ x = 0
任何数与 0 进行异或运算, 结果为其自身
x ^ 0 = x
有了上面的理论基础之后，下面来看下异或运算的几个应用。
交换两个变量的值
有个经典的笔试题：交换两个变量的值，不能使用第三个变量。
解法一
利用 Go 语言的原生 “骚操作” :
package main
import "fmt"
func main() {
x, y := 1, 2
x, y = y, x
fmt.Printf("x = %d, y = %d\n", x, y)
// 输出: x = 2, y = 1
}
当然了，如果在真实面试中这样写，只能回去等消息了。
解法二
利用加法分配率
package main
import "fmt"
func main() {
x, y := 1, 2
x += y // x = 3
y = x - y // y = 1
x -= y // x = 2
fmt.Printf("x = %d, y = %d\n", x, y)
// 输出: x = 2, y = 1
}
解法三
异或运算性质: 三个值中的任意两个值进行异或运算，都可以得出第三个值。
package main
import "fmt"
func main() {
x, y := 1, 2
x ^= y // x = 3
y ^= x // y = 1
x ^= y // x = 2
fmt.Printf("x = %d, y = %d\n", x, y)
// 输出: x = 2, y = 1
}
加密解密
异或运算可以实现简单高效的加密解密，例如:
- 明文数据为 text
- 密钥为 secret
- 密文数据为 token
# 服务端响应时，返回加密数据
token = text ^ secret
# 服务端接收到请求时，解密数据
text = token ^ secret
这个经典应用在 CSRF 攻击防范 一文中已经讲过，这里不再赘述，感兴趣的读者可以跳转阅读。
数据备份
将数据 x 和数据 y 进行异或运算得到备份数据 z, 然后将三个数据同时保存 (备份数据 z 保存到可用性更高的数据中心)，之后不论数据 x 或数据 y 损坏了，都可以根据备份数据 z 进行恢复。
简化计算
在多个值进行计算的场景中，可以根据运算定律简化计算过程:
x ^ y ^ z ^ x ^ y
上述计算式子根据交换律，可以得到:
x ^ x ^ y ^ y ^ z
根据 “任何数与自身进行异或运算，结果都为 0” 运算定律，可以得到:
0 ^ 0 ^ z = z
算法设计
异或运算经常被用于设计高效的数据结构和算法，例如之前的文章提到的 布谷鸟过滤器。
LeetCode 原题
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
要求: 必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
# 示例 1
输入：nums = [2,2,1]
输出：1
# 示例 2
输入：nums = [4,1,2,1,2]
输出：4
# 示例 3
输入：nums = [1]
输出：1
解题代码如下:
// 利用异或运算的性质:
// 1. 任何数和 0 做异或运算，结果仍然是原来的数
// 2. 任何数和其自身做异或运算，结果是 0
// 3. 异或运算满足交换律和结合律，a^b^a = b^a^a = b^(a^a) = b^0 = b
func singleNumber(nums []int) int {
res := 0
for _, v := range nums {
res ^= v
}
return res
}