Go：异或运算的妙用

概述

异或运算 通过对两个相同长度的二进制数进行逐位比较，若对应位的值不同，结果为 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 // 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 ^ y ^ z ^ x ^ y

根据 “任何数与自身进行异或运算，结果都为 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
}