本文翻译自 Florian 于 2020 年 3 月发表的一篇英文博客《That XOR Trick》。

有一大堆流行的面试问题可以通过以下两种方式之一解决：要么以合理的方式使用常见的数据结构和算法，要么以一种看似难以理解的方式使用异或运算 XOR 的某些特性。

虽然在面试中指望异或运算 XOR 解决方案似乎并不合理，但弄清楚它们的工作原理还是很有趣的。实际上，它们都基于同一个基本窍门，我们将在本文中以自下而上的方式将其推导出来。之后我们再来看 XOR 窍门的一系列应用，例如解决以下这个流行的面试题：

给定一个由 n - 1 个整数组成的数组，这些整数的范围在 1 到 n 之间。除了一个数字缺失之外，其余每个数字均只出现一次。找出这个缺失的数字。

当然，有许多直截了当的方法可以解决这个问题，但还有一种可能令人意想不到的方法——使用 XOR。

XOR

XOR 是一种应用于位的逻辑运算符。我们用 ^ 表示它。如果它作为输入携带的两个位是相同的，那么它的结果就为 0，否则就为 1。这实现了一个异或运算，即只有一个参数必须是 1 才能使最终结果为 1。我们可以使用真值表来证明这一点：

x y x ^ y
0 0 0
0 1 1
1 0 1
1 1 0

大多数编程语言将 ^ 实现为按位运算符，这意味着 XOR 单独应用于位串（例如一个字节）中的每个位。

例如： 

1
0011 ^ 0101 = 0110

因为 

1
2
3
4
5
6
7
8
0 ^ 0 = 0 

0 ^ 1 = 1 

1 ^ 0 = 1 

1 ^ 1 = 0

因此，我们可以将 XOR 应用于任何事物，而不仅仅是布尔值。

推导出一些有用的特性

我们可以从之前的定义中推导出一堆特性。下面我们一一梳理一遍，然后组合起来解决前面提到的面试题。

恒等律：x ^ 0 = x

如果 XOR 的两个参数之一为 0，则剩余的那个参数就是结果。该结论可通过检查以下真值表中 y = 0 的行（即第一行和第三行）直接得出：

x y x ^ y
0 0 0
0 1 1
1 0 1
1 1 0

归零律：x ^ x = 0

如果两个参数相同，则结果始终为 0。同样，我们可以通过检查真值表得出该结论。这次我们检查 x = y 的行，即第一行和最后一行。

x y x ^ y
0 0 0
0 1 1
1 0 1
1 1 0

直观地说，这意味着如果我们对相同的参数应用 XOR，它们会相互抵消。

交换律：x ^ y = y ^ x

XOR 是可交换的，这意味着我们可以更改应用 XOR 的顺序。为了证明这一点，我们可以检查 x ^ y 和 y ^ x 的真值表：

x y x ^ y y ^ x
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 0

正如我们所看到的，x ^ y 和 y ^ x 总是以相同的值结束。

XOR 操作序列

通过结合以上这些规律，我们可以推断出以下这个一切背后的核心启迪：

XOR 诀窍：如果存在一个 XOR 操作系列 a ^ b ^ c ^ ...，那么我们可以删除所有成对的重复值而不影响结果。

交换律允许我们可以对 XOR 进行重新排序，以便使重复的元素彼此相邻。由于 x ^ x = 0 和 a ^ 0 = a，所以每一对重复值对结果没有影响。

让我们来看一个例子：

1
2
3
4
 a ^ b ^ c ^ a ^ b      # 应用交换率
= a ^ a ^ b ^ b ^ c     # 应用 x ^ x = 0
= 0 ^ 0 ^ c             # 应用 x ^ 0 = x (和交换率)
= c

因为 ^ 是一个按位运算符，所以不管 a、b 和 c 是什么类型的值，这都会起作用。这个诀窍实际上是 XOR 在许多情况下看似神奇使用的核心。

应用一：就地交换

在解决找出缺失数字的问题之前，我们先从这个更简单的问题开始：

就地交换两个值 x 和 y，即不使用任何辅助变量。

实际上使用以下三条 XOR 指令可以轻松解决该问题：

1
2
3
x ^= y
y ^= x
x ^= y

看起来好像有点神秘。为什么执行这三条指令最终会交换 x, y 的值呢？

为了弄清它的原理，我们一起把这些指令一步一步地过一遍。每条指令后的注释显示 (x, y) 的当前值：

1
2
3
x ^= y # =>                      (x ^ y, y)
y ^= x # => (x ^ y, y ^ x ^ y) = (x ^ y, x)
x ^= y # => (x ^ y ^ x, x)     = (y, x)

我们可以看到，这实际上只是使用了前文推导出来的特性而已。

这里的基本原理就是将 x ^ y 放在一个变量中，将 x 放在另一个变量中，这样就可以让我们完美地重建 y。一旦 x ^ y 被存储（指令 1），我们就可以将 x 放入另一个变量（指令 2），然后再用它来将 x ^ y 更改为 y（指令 3）。

应用二：寻找缺失的数字

现在，我们来解决本文开头提出的问题：

给定一个由 n - 1 个整数组成的数组 A，这些整数的范围在 1 到 n 之间。除了一个数字缺失之外，其余每个数字均只出现一次。找出那个缺失的数字。

当然，有很多直截了当的方法可以解决这个问题，不过这里我们准备使用 XOR 的方法来解决这个问题。

从 XOR 技巧我们知道，对于一条 XOR 序列的语句，我们可以移除所有成对的重复元素。不过，如果我们只是对给定数组中的所有值进行异或，我们就不能用到该技巧，因为没有重复元素：

1
A[0] ^ A[1] ^ ... ^ A[n - 2]

注意 A[n - 2] 是 n - 1 个元素数组的最后一个索引。

此外，我们还可以把 1 和 n 之间的所有值也加进来一并进行异或：

1
1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 2]

这样，我们得到的 XOR 操作序列，它们的元素出现如下：

  • 给定数组中的所有值现在会出现两次：
    • 一次是 1 到 n 之间的所有值；
    • 一次是本来就存在于给定的原始数组中。
  • 缺失数字只会出现一次：
    • 一次是 1 到 n 之间的所有值。

如果对所有这些值进行异或，根据异或技巧，实质上就是移除了所有出现两次的数字。也就是说，留下来的数字恰好就是我们一开始要寻找的缺失数字。

编码后，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
def find_missing(A, n):
  result = 0

  # XOR of all the values from 1 to n
  for value in range(1, n + 1):
    result ^= value

  # XOR of all values in the given array
  for value in A:
    result ^= value

  return result

单看代码的话，看起来像是一个难以理解的算法。然而，当知道了 XOR 技巧的原理时，就变得相当简单。我认为这也说明了为什么在面试中指望这个解决方案是不合理的：它要求了解一个非常特殊的技巧，但除此之外并不需要太多算法层面上的思考。

在继续说明下一个应用之前，这里再多说两点。

推广到整数之外

尽管到目前为止我们一直讨论的都是 1 到 n 的整数，不过并不仅限于整数。实际上，前面的算法适用于
(1) 一些潜在元素集 和
(2) 一组实际出现的元素
的任何情况。这些集合可能仅在缺失那个元素上有所不同。这对整数很有效，因为潜在元素的集合正好对应于从 1 到 n 的元素。

可以想象元素不是 1 到 n 的整数情况的应用：

  • 潜在元素集是 Person 对象，我们要从值列表中找到缺失的 Person
  • 潜在元素集是图中的所有节点，我们要找出缺失的节点
  • 潜在元素的集合是一般的整数（不一定是从 1 到 n），我们要找到缺失的那个整数

使用算术运算符而不是 XOR

如果读到这里，该算法看起来仍有点神奇的话（我希望不是），那么考虑如何使用算术运算符获得相同的结果可能会有所帮助。这实际上相当简单：

1
2
3
4
5
6
7
8
9
10
11
12
def find_missing(A, n):
  result = 0

  # Add all the values from 1 to n
  for value in range(1, n + 1):
    result += value

  # Subtract all values in the given array
  for value in A:
    result -= value

  return result

把所有潜在的整数相加，然后减去实际出现的整数。该解决方案不是很好，因为需要处理数值溢出情况和需要元素的某些属性类型支持 +、- 运算。不过元素相互抵消的逻辑是一样的，因为每个元素出现次数是确定的（一次为正，一次为负）。

应用三：找出重复的数字

有趣的是：我们可以把完全相同的解决方案应用到类似的面试题：

给定一个由 n + 1 个整数组成的数组 A，这些整数的范围在 1 到 n 之间。除了一个数字重复之外，其余每个数字均只出现一次。找出这个重复的数字。

思考一下，如果我们只运用与之前的解决方案完全相同的算法，会出现什么情况。我们会得到 XOR 序列语句，其中元素出现如下：

  • 给定列表中的重复的值出现了 3 次：

    • 一次是 1 到 n 之间的所有值；
    • 两次是本来就存在于给定的原始数组中（因为重复）。

  • 给定列表中的所有其他值出现两次：

    • 一次从取 1 到 n 之间的所有值
    • 一次是本来就存在于给定的原始数组中。

如前所述，所有成对的重复元素会相互抵消。这意味着，剩下的恰好就是我们正要寻找的元素——在原始数组中重复的元素。此元素出现 3 次，结合 XOR，简化后正是此元素本身：

1
2
3
 x ^ x ^ x
= x ^ 0
= x

其他所有元素相互抵消，因为它们恰好出现两次。

应用四：找出两个缺失/重复的数字

实际上我们可以更进一步，考虑以下稍微有些难度的问题：

给定一个由 n - 2 个整数组成的数组 A，这些整数的范围在 1 到 n 之间。除了两个数字缺失之外，其余每个数字均只出现一次。找出这两个缺失的数字。

和之前一样，在找出两个重复的数字而不是两个缺失的数字时，问题是完全等价的。

相信你已经猜到怎么做了，不过还是延用之前的讲述方法，以完全相同的方式开始：思考一下，如果我们使用之前的 XOR 算法，会出现什么情况。如果这样做，我们将再次得到 XOR 序列语句，除了我们正要寻找的那两个，其余所有元素相互抵消。

我们用 u 和 v 来表示这两个缺失的元素，主要是因为我们之前没有用到这些字母。应用前面的算法后，我们就剩下 u ^ v。接下来该怎么做？我们需要以某种方式从这个值中提取 u 和 v，但现在还不清楚怎么做。

根据查看 u ^ v 的结果进行分区

幸运的是，我们可以通过运用本文前面讲过的内容来弄清楚该怎么做。

本文早些时候提到：

如果 XOR 作为输入携带的两个位是一样的，则结果为 0，否则为 1。

也就是说，对于 u ^ v 结果中的各个位的值，如果为 0 就表示 u 和 v 在该位具有相同的值。如果为 1 就表示 u 和 v 在该位具有不同的值。

现在，我们先从 u ^ v 结果中找到第一个值为 1 的位（记为 i），根据上面的结论，u 和 v 在第 i 位的值一定是不同的。然后，根据元素在这个位的值（0 或 1），对数组 A 和从 1 到 n 的数字集中的元素进行分区。最终得到的两个分区，每个分区包含两个集合：

  1. 分区 0（元素第 i 位为 0）
    1. 从 1 到 n 的数字集合，其中元素的第 i 位为 0
    2. 数组 A，其中元素的第 i 位为 0
  2. 分区 1（元素第 i 位为 1）
    1. 从 1 到 n 的数字集合，其中元素的第 i 位为 1
    2. 数组 A，其中元素的第 i 位为 1

因为 u 和 v 在位置 i 上不同，所以这两个元素肯定分布在不同的分区中。

简化问题

接下来，我们运用本文早些时候提到的另一个见解：

尽管到目前为止我们一直讨论的都是 1 到 n 的整数，不过并不仅限于整数。实际上，前面的算法适用于
(1) 一些潜在元素集 和
(2) 一组实际出现的元素
的任何情况。这些集合可能仅在缺失（或重复）那个元素上有所不同。

这两个集合（指潜在元素集和实际出现的元素集）与我们在每个分区中的集合完全对应。因此，我们可以通过将这个想法用于其中一个分区来搜索元素 u，从而找到缺失的元素。然后再将其用于另一个分区来找到 v。

这实际上是一个很好的解决方法：我们有效地将这个新问题简化为我们先前解决的问题的一般形式。

达到极限

你可能会想尝试更进一步，旨在解决两个以上缺失值的问题。我没有对此进行仔细的思考，但我认为这是我们停止使用 XOR 的地方。如果缺失（或重复）两个以上的元素，则无法分析 XOR 结果上各个位的值，因为无论是 0 还是 1 都可能有多种组合作为结果。

问题似乎需要更复杂的解决方案，这些解决方案不再基于 XOR。

最后的想法

如前所述，基于此诀窍的面试题似乎不是一个好主意。他们需要知道一个稍微有点晦涩的诀窍，但是一旦知道了这个诀窍，就没有什么需要解决的了（除了应用四）。也几乎没有一种方法可以展示算法思维（除了简化），也没有很好的方法来利用数据结构。

然而，我发现了解这个诀窍实际上是如何工作的非常酷。 XOR 似乎具有解决所有这些问题的正确特性。像 XOR 这样基本的东西可以用来构建这里描述的所有东西，这也很美妙。

感谢 Eugen 的讨论促成了这篇文章。一起弄清楚所有这些是如何工作的很有趣。

（END）