异或运算

2022-10-14

异或运算(exclusive or)又记作XOR，一般用插入符号(caret)^表示，其可以看到是更加单纯的或运算(|)。我们知道，或运算的规则是：

a=1，b=1，a|b=1 ①
a，b任意一个为1，a|b=1 ②

异或运算则是去除了或运算中的规则①，即只有a、b相异时，结果才为真，其他情形都为假。因此异或运算的真值表为：

0^0 = 0
0^1 = 1
1^0 = 1
1^1 = 0

与0异或，其值不变；与1异或，相当于取反。

异或运算有一些特殊的性质，利用这些性质，可以解决特定的问题。这也是本文所要讨论的重点。

1. 异或运算的性质 #

交换律： A^B = B^A
结合律： (A^B)^C = A^(B^C)
对于任意数A，都有A^A=0，A^0=A
自反性：A^B^B = A

其中，自反性尤其重要。其内涵为，对于任意数A，给定任意运算因子B，做偶数次异或运算后，得到A本身。异或运算的很多应用，都是基于自反性。

2. 异或运算的典型应用 #

2.1 交换2个数 #

一般地，如果想交换2个数，我们会引入一个中间变量来完成这一操作。但是，利用异或运算，可以在不需要额外空间的情况下完成2个数的交换：

1var a = 1
2var b = 2
3// swap
4a = a^b
5b = b^a // b^a^b = a
6a = a^b // a^b^b^a^b = b
7println("a=$a, b=$b") // a = 2, b=1

在kotlin中，交换2个数可以这样实现：
1var a = 1
2var b = 2
3a = b.also { b = a}

2.2 经典面试题 #

找出唯一数 #

在一个整数数组中，仅存在唯一一个不重复的数字，其他的数字均出现2次或2次以上（偶数次），找出那个不重复的数字。

如果熟悉异或运算的自反性，阅读题干就能自然联想到，使用异或运算能够快速求解：

设唯一元素为N，那么

A^B^C^...N^D^E^F...

由于除了N外，A、B、C、D、E、F都出现偶数次，其异或运算结果为0，故原式即为
N^0

当然，此题还有其他解法，如典型的使用嵌套循环，即可找出唯一数：

 1fun solution(arr: IntArray): Int {
 2        for (j in arr) {
 3            var count = 0
 4            for (k in arr) {
 5                if (j == k) count++
 6            }
 7            if (count == 1) return j
 8        }
 9        return -1
10    }

找出重复数 #

将1-999放在一个容量为1000的集合中，只有1个元素重复，其他的元素均只出现1次，找出这个重复的元素。

在数据不溢出的情况下，此题可通过所有元素和轻松解出。不过，我们讨论的是使用异或运算的性质来解题。

记重复数为N，
设 1^2^3^...^(N-1)^N^N^(N+1)^...^997^998^999 = T
则 1^2^3^...^(N-1)^N^(N+1)^...^997^998^999 = T^N
故 N = T^T^N

上述题还有一相关变体：

一个数组包含 n-1 个成员，这些成员是 1 到 n 之间的整数，且没有重复，请找出缺少的那个数字。

同样地，对集合中的元素和1-n的有序序列数做异或运算，既可得到缺少的那个值（只出现一次）。

2.3 加解密 #

若有明文A以及密钥K，那么密文S可以由

A^K=S

获得。同理，当需要解密时，可以使用

S^K=A 获得明文。

备份文件 #

若有A、B两个文件，只要A、B不同时损坏，即可以通过异或运算的备份T来恢复其中一个损坏的文件：

A^B=T

若文件A损坏，则可以通过

T^B=A

来恢复损坏的文件A。反之亦然。

xf&pl