谈谈异或运算
本文翻译自 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 | 0 ^ 0 = 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 | a ^ b ^ c ^ a ^ b # 应用交换率 |
因为 ^
是一个按位运算符,所以不管 a
、b
和 c
是什么类型的值,这都会起作用。这个诀窍实际上是 XOR 在许多情况下看似神奇使用的核心。
应用一:就地交换
在解决找出缺失数字的问题之前,我们先从这个更简单的问题开始:
就地交换两个值 x 和 y,即不使用任何辅助变量。
实际上使用以下三条 XOR 指令可以轻松解决该问题:
1 | x ^= y |
看起来好像有点神秘。为什么执行这三条指令最终会交换 x, y 的值呢?
为了弄清它的原理,我们一起把这些指令一步一步地过一遍。每条指令后的注释显示 (x, y) 的当前值:
1 | x ^= y # => (x ^ y, y) |
我们可以看到,这实际上只是使用了前文推导出来的特性而已。
这里的基本原理就是将 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 | def find_missing(A, n): |
单看代码的话,看起来像是一个难以理解的算法。然而,当知道了 XOR 技巧的原理时,就变得相当简单。我认为这也说明了为什么在面试中指望这个解决方案是不合理的:它要求了解一个非常特殊的技巧,但除此之外并不需要太多算法层面上的思考。
在继续说明下一个应用之前,这里再多说两点。
推广到整数之外
尽管到目前为止我们一直讨论的都是 1 到 n 的整数,不过并不仅限于整数。实际上,前面的算法适用于
(1) 一些潜在元素集 和
(2) 一组实际出现的元素
的任何情况。这些集合可能仅在缺失那个元素上有所不同。这对整数很有效,因为潜在元素的集合正好对应于从 1 到 n 的元素。
可以想象元素不是 1 到 n 的整数情况的应用:
- 潜在元素集是
Person
对象,我们要从值列表中找到缺失的Person
- 潜在元素集是图中的所有节点,我们要找出缺失的节点
- 潜在元素的集合是一般的整数(不一定是从 1 到 n),我们要找到缺失的那个整数
使用算术运算符而不是 XOR
如果读到这里,该算法看起来仍有点神奇的话(我希望不是),那么考虑如何使用算术运算符获得相同的结果可能会有所帮助。这实际上相当简单:
1 | def find_missing(A, n): |
把所有潜在的整数相加,然后减去实际出现的整数。该解决方案不是很好,因为需要处理数值溢出情况和需要元素的某些属性类型支持 +
、-
运算。不过元素相互抵消的逻辑是一样的,因为每个元素出现次数是确定的(一次为正,一次为负)。
应用三:找出重复的数字
有趣的是:我们可以把完全相同的解决方案应用到类似的面试题:
给定一个由 n + 1 个整数组成的数组 A,这些整数的范围在 1 到 n 之间。除了一个数字重复之外,其余每个数字均只出现一次。找出这个重复的数字。
思考一下,如果我们只运用与之前的解决方案完全相同的算法,会出现什么情况。我们会得到 XOR 序列语句,其中元素出现如下:
给定列表中的重复的值出现了 3 次:
- 一次是 1 到 n 之间的所有值;
- 两次是本来就存在于给定的原始数组中(因为重复)。
给定列表中的所有其他值出现两次:
- 一次从取 1 到 n 之间的所有值
- 一次是本来就存在于给定的原始数组中。
如前所述,所有成对的重复元素会相互抵消。这意味着,剩下的恰好就是我们正要寻找的元素——在原始数组中重复的元素。此元素出现 3 次,结合 XOR,简化后正是此元素本身:
1 | x ^ x ^ 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 的数字集中的元素进行分区。最终得到的两个分区,每个分区包含两个集合:
- 分区 0(元素第 i 位为 0)
- 从 1 到 n 的数字集合,其中元素的第 i 位为 0
- 数组 A,其中元素的第 i 位为 0
- 分区 1(元素第 i 位为 1)
- 从 1 到 n 的数字集合,其中元素的第 i 位为 1
- 数组 A,其中元素的第 i 位为 1
因为 u
和 v
在位置 i
上不同,所以这两个元素肯定分布在不同的分区中。
简化问题
接下来,我们运用本文早些时候提到的另一个见解:
尽管到目前为止我们一直讨论的都是 1 到 n 的整数,不过并不仅限于整数。实际上,前面的算法适用于
(1) 一些潜在元素集 和
(2) 一组实际出现的元素
的任何情况。这些集合可能仅在缺失(或重复)那个元素上有所不同。
这两个集合(指潜在元素集和实际出现的元素集)与我们在每个分区中的集合完全对应。因此,我们可以通过将这个想法用于其中一个分区来搜索元素 u
,从而找到缺失的元素。然后再将其用于另一个分区来找到 v
。
这实际上是一个很好的解决方法:我们有效地将这个新问题简化为我们先前解决的问题的一般形式。
达到极限
你可能会想尝试更进一步,旨在解决两个以上缺失值的问题。我没有对此进行仔细的思考,但我认为这是我们停止使用 XOR 的地方。如果缺失(或重复)两个以上的元素,则无法分析 XOR 结果上各个位的值,因为无论是 0 还是 1 都可能有多种组合作为结果。
问题似乎需要更复杂的解决方案,这些解决方案不再基于 XOR。
最后的想法
如前所述,基于此诀窍的面试题似乎不是一个好主意。他们需要知道一个稍微有点晦涩的诀窍,但是一旦知道了这个诀窍,就没有什么需要解决的了(除了应用四)。也几乎没有一种方法可以展示算法思维(除了简化),也没有很好的方法来利用数据结构。
然而,我发现了解这个诀窍实际上是如何工作的非常酷。 XOR 似乎具有解决所有这些问题的正确特性。像 XOR 这样基本的东西可以用来构建这里描述的所有东西,这也很美妙。
感谢 Eugen 的讨论促成了这篇文章。一起弄清楚所有这些是如何工作的很有趣。
(END)