那个异或技巧

可以通过以下两种方法之一解决一整套受欢迎的面试问题：以明智的方式使用通用数据结构和算法，或者以似乎难以理解的方式使用XOR的某些属性。

虽然在访谈中期望XOR解决方案似乎是不合理的，但弄清楚它们的工作方式却很有趣，事实证明，它们都是基于相同的基本技巧，我们将在此以自底向上的方式得出之后。我们将研究该XOR窍门™的大量应用程序，例如解决此热门面试问题：

您会得到一个由n-1个整数组成的数组，它们的范围在1到n之间。除缺少一个数字外，所有数字仅出现一次。找到这个遗漏的号码。

当然，有很多直接的方法可以解决此问题，但是使用XOR也许也很令人惊讶。

XOR是一个逻辑运算符，对位进行运算，用^表示，如果作为输入的两位相同，则结果为0，否则为1，这实现了异或运算，即一个参数具有为1表示最终结果为1。我们可以使用真值表来显示此结果：

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

0 ^ 0 = 00 ^ 1 = 11 ^ 0 = 11 ^ 1 = 0

我们可以从先前的定义中得出一堆属性。让我们逐一进行研究，然后组合它们以解决前面提到的采访问题。

如果XOR的两个参数之一为0，则剩下的参数为结果，这是通过检查y = 0的行（即第一行和第三行）直接从真值表得出的。

如果两个参数相同，则结果始终为0，再次，我们可以通过检查真值表来说服自己这是真的，这次我们必须检查x = y的行，即第一行和最后一行。

直观地讲，这意味着如果将XOR应用于相同的参数，它们将互相抵消。

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

如我们所见，x ^ y和y ^ x总是以相同的值结尾。

通过结合所有这些，我们可以推断出将要遵循的一切背后的中心洞察力：

XOR技巧：如果我们有一系列XOR操作a ^ b ^ c ^ ...，那么我们可以删除所有重复值对，而不会影响结果。 交换性使我们可以对XOR的应用进行重新排序，以使重复的元素彼此相邻。由于x ^ x = 0和a ^ 0 = a，每对重复值对结果均无影响。 a ^ b ^ c ^ a ^ b＃可交换性= a ^ a ^ b ^ b ^ c＃使用x ^ x = 0 = 0 ^ 0 ^ c＃使用x ^ 0 = x（和可交换性）= c 因为^是按位运算符，所以无论a，b和c是哪种值，它都将起作用。这个想法实际上是在许多情况下如何神奇地使用XOR的核心。 在解决发现遗漏号码的问题之前，让我们从一个简单的问题开始： 事实证明，使用以下三个XOR指令可以轻松解决此问题： 这似乎有点神秘。如果这样做，为什么我们最终要交换x，y？

要了解其工作原理，请逐步进行操作。每条指令后的注释均显示（x，y）的当前值：

x ^ = y＃=＆gt; （x ^ y，y）y ^ = x＃=＆gt; （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语句意味着我们可以删除所有重复的参数。但是，如果仅对给定列表中的所有值进行XOR，则由于没有重复项，因此无法应用此技巧：

我们还可以做的是对1到n之间的所有值进行XOR：

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

如果我们对所有这些都进行XOR，那么由于XOR技巧，我们实际上会删除出现两次的所有值，这意味着我们剩下的缺失值恰好是我们最初寻找的值。

def find_missing（A，n）：结果= 0＃范围（1，n + 1）中值从1到n的所有值的XOR：结果^ = value＃给定数组中A中值的所有值的XOR ：结果^ =值返回结果

仅看代码，这似乎是很难理解的算法，但是当知道XOR技巧是如何工作时，它就变得微不足道了，我认为这也说明了为什么在面试中期望这种解决方案是不合理的：这要求对特定技巧的了解，但除此之外没有太多算法思考。

在继续进行下一个应用程序之前，让我继续讲两点。

到目前为止，虽然我们处理的是从1到n的整数，但这并不是必需的。实际上，以前的算法可以在以下情况下工作：（1）一些潜在元素集和（2）实际出现一组元素。集合可能只在一个缺失的元素上有所不同。这对于整数很好，因为潜在元素的集合刚好对应于1到n的元素。

潜在元素的集合是Person对象，我们应该从值列表中找到缺少的Person。

潜在元素集是图中的所有节点，我们正在寻找缺失的节点

潜在元素的集合通常是整数（不一定是1到n），我们想找到一个缺失的整数

如果该算法似乎仍然有些神奇（我希望它不会），那么可能会有助于考虑使用算术运算符如何实现相同的结果。这实际上非常简单：

def find_missing（A，n）：result = 0＃为范围（1，n + 1）中的值添加从1到n的所有值：result + = value＃减去给定数组中A中的所有值：result -=值返回结果

我们将所有可能的整数相加然后减去实际出现的整数。解决方案不是很好，因为一个人需要处理溢出并且因为它需要元素的类型来支持带有特定属性的+，-但是它具有元素彼此抵消的相同逻辑是因为它们出现一定次数（一次为正，一次为负）。

这就是有趣的地方：我们可以将完全相同的解决方案应用于相似的面试问题：

您将得到一个n + 1个整数的数组A，它们的范围在1到n之间。除一个数字重复外，所有数字仅出现一次。查找此重复的号码。

让我们考虑一下，如果仅应用与上一个解决方案完全相同的算法，将会发生什么。我们将获得一系列XOR语句，其中元素如下所示：

如前所述，所有重复的元素相互抵消，这意味着我们只剩下要寻找的东西：在原始数组中重复的元素，这个元素出现了3次，再加上XOR，就减少到那个元素：

事实证明，我们可以更进一步地考虑以下问题（稍微困难一点）：

您会得到一个由n-2个整数组成的数组A，范围在1到n之间。除缺少两个数字外，所有数字仅出现一次。找到这两个缺失的数字。

和以前一样，查找两个重复的数字而不是两个丢失的数字时，问题完全相同。

我敢肯定，你猜对了，但是我们会坚持以前的工作，并以完全相同的方式开始：让我们考虑一下如果使用以前的XOR算法会发生什么，如果这样做，我们将再次得到一系列XOR语句其中所有元素彼此抵消，我们正在寻找的两个元素除外。

我们将用u和v表示这些元素，主要是因为我们之前没有使用过这些字母，所以在应用之前的算法后，我们剩下u ^ v，我们该怎么办？我们不知何故需要从该值中提取u和v，但目前尚不清楚这样做。

幸运的是，我们可以使用前面已经讲过的方法弄清楚该怎么做。让我们考虑一下： 如果XOR作为输入的两位相同，则结果为0，否则为1。 如果我们分析u ^ v中的各个位，则每个0表示该位在u和v中具有相同的值。每个1表示该位不同。 使用这个函数，我们找到u ^ v中的第一个1，即u和v必须相异的第一个位置i，然后根据该位将A以及从1到n的数字进行分区。 我们最终得到两个分区，每个分区包含两个集合： 分区0第1位为0时从1到n的所有值的集合 分区1第1位为1时从1到n的所有值的集合 由于u和v在位置i上不同，因此我们知道它们必须位于不同的分区中。

到目前为止，虽然我们处理的是从1到n的整数，但这并不是必需的。实际上，以前的算法可以在以下情况下工作：（1）一些潜在元素集和（2）实际出现一组元素。集可能仅在一个缺失（或重复）元素上有所不同。

这两个集合与每个分区中的集合完全对应。因此，我们可以通过将这个想法应用于一个分区并找到丢失的元素来搜索u，然后将其应用于另一个分区来查找v。

实际上，这是解决问题的一种不错的方法：我们将这个新问题有效地简化为我们先前解决的问题的更一般的版本。

一个人可能会尝试进一步解决这个问题，并试图解决两个以上缺失值的问题。我没有给出过多的想法，但是我认为这是我们停止对XOR成功的地方。如果缺少两个以上的元素（或重复），然后分析单个位会失败，因为结果0和1都有几种组合。

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

如前所述，基于这个技巧的面试问题似乎不是一个好主意，他们需要知道一个稍微晦涩的技巧，但是一旦知道了这个技巧，就没什么要解决的了（除了应用程序4）。也几乎没有一种显示算法思维的方法（除了归约法），也没有利用数据结构的好方法。

但是，我发现找出这个技巧是如何工作真的很酷.XOR似乎具有正确的属性可以解决所有这些问题，并且可以使用像XOR这样基本的东西来构建它也很漂亮。这里描述的所有东西。

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