[翻译 & 补充] - 异或操作小技巧

译者注

之前刷leetcode的时候遇到一些题解使用XOR的解法 真的‘惊为天人’。今天看到阮一峰老师分享了一篇文章异或教程，参考链接里有此篇原文，觉得很有意思，遂翻译翻译，加深理解，巩固知识。

如果你也遇到过什么让你惊艳的异或技巧，欢迎评论分享呀~

正文开始

原文发布时间: 2020-03-15

有很多很受欢迎的面试问题都可以通过以下两种方式来解决： 要么使用通用的数据结构和算法,要么以看似难以理解的方式使用XOR的某些特性。

虽然总是期待在面试中使用XOR解法不太合理，但弄清楚它们是如何工作的还是很有趣的。事实证明，它们都基于相同的技巧，我们将在这篇文章中慢慢演示推导。然后，我们将举一些异或技巧的应用，比如解决这个常见的面试问题：

当然啦，有许多直接的方法可以解决这个问题，但使用异或绝对会让人眼前一亮。

异或操作符

XOR是基于二进制的位运算。用^符号表示。如果两个操作数相同，结果为0，否则结果为1。这其实是一种排他性的或运算。 只有一个参数是1时，最终结果才会是1

异或运算真值表

大多数编程语言将^作为位运算符来实现，这意味着XOR将其操作数当作32位的比特序列（由0和1组成）而不是十进制、十六进制或八进制数值。

举个栗子：

0011 ^ 0101 = 0110

因为：

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

正因如此，万物皆可异或，而不仅仅是只能操作布尔值。

异或运算定律

我们可以从前面的定义推导出一些特性，然后运用这些特性去解决面试题。一个个来，别着急！

1. 一个值与0的运算，等于其本身

x ^ 0 = x

可以从真值表第1、2、3行看出来。

2. 同值异或得0

x ^ x = 0

可以从真值表1、4行看出,当x = y 时，结果时0。

3. x与 -1的运算，等于x的反码

x ^ -1 = ~x

4. 可交换性

x ^ y = y ^ x

5. 结合性

x ^ (y ^ z) = (x ^ y) ^ z

结合以上，我们来看个小demo：

  a ^ b ^ c ^ a ^ b     // 交换性法则
= a ^ a ^ b ^ b ^ c     // 使用 x ^ x = 0法则
= 0 ^ 0 ^ c             // 使用x ^ 0 = x法则和交换性法则
= c

面试题1： 交换值

来做个题：

我相信任何程序员都能在使用一个临时变量的情况下完成交换值这个基本操作，但是题目规定不能使用新变量。 这个时候异或来了！！

x ^= y
y ^= x
x ^= y

是不是非常的Amazing！！来让我们来一步一步看看怎么实现的，每行的注释表示当前的(x， y)值

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)。

面试题2：找到丢失的数字

再来看看文章开头说的问题：

当然有很多直接的方法做这题，今天让我们来看看异或怎么解决这题。

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

上面这个式子中，每个数组成员都会出现两次，相同的值进行异或运算就会得到 0。只有缺少的那个数字出现一次，所以最后得到的就是这个值。 写下代码（原文是用的Python, 我这里用JS写下，对Python感兴趣的看看原文）

function findMissing(arr, n) {
  let result = 0;
  // XOR of all values in the given array
  for (let i = 0; i < arr.length; i++) {
    result ^= arr[i]
  }
  //  XOR of all the values from 1 to n
  for (let i = 1; i <= n ; i++) {
    result ^= i
  }
  return result
}

仅看代码，这似乎是一个难以理解的算法。但是，当知道XOR技巧的工作原理时，它就变得so easy了。 我想这也说明了为什么在面试中期待这个解法是不合理的：它需要了解一种非常具体的技巧，但不需要太多的算法思维。在我们继续下一个题之前，让我接着说两点：

在整数之外推广应用

到目前为止，我们研究的是从1到n的整数，但这不是必需的。事实上，前面的算法适用于以下情况:

(1) 有一组潜在元素

(2) 有一组元素实际出现。

(3) 两个集合只在缺少的一个元素上有所不同。

这对于整数来说很有效因为潜在元素的集合是从1到n的元素。

但在实际应用中，我们会遇到以下情况：

1）潜在元素的集合是Person对象，我们需要在对象中找到缺失的属性

2）潜在元素的集合是图中的所有节点，我们需要寻找一个缺失的节点

3）潜在元素的集合是普通的整数(不一定是从1到n)，我们想找到一个缺失的整数

使用普通运算符解题

如果上述算法看起来还是有点困惑的话，思考一下如何使用算术运算符来达到同样的结果可能会有所帮助。

 function findMissing(arr, n) {
    let result = 0;
    // Subtract all values in the given array
    for (let i = 0; i < arr.length; i++) {
      result += arr[i]
    }  
    // Add all the values from 1 to 
    for (let i = 1; i <= n ; i++) {
      result -= i
    }
    return result
  }

加法的速度没有异或运算快，而且需要额外的空间。如果数字比较大，还有溢出的可能。

面试题3： 找到重复的数字

有趣的是:我们可以将同样的答案应用到类似的面试问题上：

上代码。Amazing！ 还是面试题2的解法。

function findDuplicated(arr, n) {
  let result = 0;
  for (let i = 0; i < arr.length; i++) {
    result ^= arr[i]
  }
  for (let i = 1; i <= n ; i++) {
    result ^= i
  }
  return result
}

结合XOR 技巧，简化成以下解题思路：

  x ^ x ^ x
= x ^ 0
= x

其他元素都抵消掉了因为它们刚好出现两次。

面试题4： 找到2个丢失/重复的数字

接下来我们可以更进一步。考虑下面这个稍微难一点的问题

找两个重复的数字解法相同，这里我们就不说重复的情况了。

我想你已经猜到了，但我们还和之前一样，慢慢推导一下。让我们考虑一下如果我们使用之前的异或算法会发生什么：我们将再次得到一个异或语句，其中所有元素都相互抵消，除了我们正在寻找的两个元素。

我们用u和v表示这2个元素（为啥用u，v: 因为之前没有用过这俩字母）。在应用了前面的算法之后，我们剩下u ^ v，但是怎么去提取u和v呢？

将u v 按位操作

想想之前的定律： 同值异或得0，否则得1。

我们分析下u ^ v中的每个字节：每一个0都意味着这个字节在u和v中都有相同的值。每个1则表示u和v中字节不同。

基于此，我们能在u ^ v中找到第一个1，假设是第 i 位，表示u ^ v在第 i 个字节上不同。

我们可以得到2个分区：

1). 0的分区

a). 1-n中所有第 i 位为 0 的数字集合

b). A中第 i 位为0的 数字集合

2). 1的分区

a). 1-n中所有第 i 位为 1 的 数字集合

b). A中第 i 位为1的数字集合

因为u和v在位置 i 是不同的，我们知道它们在不同的分区里。即 u 和 v 一个在 0的分区里，一个在1的分区里。

简化问题

接下来，我们可以用下之前说到的结论：

这完全对应于我们在每个分区中的集合！ 因此，我们可以将这个思想应用到其中一个分区中找到缺少的元素来寻找u，然后将它应用到另一个分区中找到v！！

这实际上是一个很好的解决方法: 我们有效地将这个新问题简化为通用解法。

举个栗子

可能你对上面的一通文字描述一头雾水，那么我来举个例子说明下，可能更好理解一些：

假设 A = [ 1, 3 ], n = 4, 当然人眼一下子就看出来丢了 2， 4。可是怎么让计算机懂呢。

1-4对应十进制二进制对应表：

数组A中数字十进制二进制对应表

根据算式：

 1 ^ 2 ^ 3 ^ 4 ^ 2 ^ 3 
 = 1 ^ 4
 = 5

将 5 转换成二进制得到： 0101

我们从左至右遍历得出 出现第一个1的位置索引是1 , 即 i = 1（为了方便 从左至右遍历）。

接下来我们进行分组：

1). 0的分区

a) 1-4中所有第 i 位为 0 的数字集合 ==> [1, 2, 3]

b) A中第 i 位为 0 的 数字集合      ==> [1 , 3]

2). 1的分区

a) 1-n中所有第 i 位为 1 的 数字集合 ==> [4]

b) A中第 i 位为1的数字集合         ==> []

容易得出，u， v 一个在 0的分区，一个在1的分区

对于这两个分区中的集合：a和b中只有一个数字不同 ！ 使用之前的异或技巧就可以解决问题?！

talk is cheap

show me the code:

function getTwoMissing(arr, n) {
  const result = findMissing(arr, n)
  const toBinary = parseInt(result).toString(2)
  // 寻找第一个1出现的位置
  let index = toBinary.indexOf('1');
  // 构建分区得到两个最简集合
  // 得到 u、v
  // 翻车！！我写不下去了?
}

sorry 我写不下去了！！这题想使用异或技巧让我感觉有点恶心~~ 还不如我直接使用暴力法构建map去查找?

挑战极限

有人可能会尝试更进一步，以解决超过两个丢失值的问题为目标。我并没有过多地考虑这个问题。但我认为使用XOR只能做这么多了。如果丢失(或重复)的元素超过两个，则分析单个字节会失败，因为0和1的结果可能有几种组合。

这个问题似乎需要更复杂的解法，而这些解法不再基于异或。更复杂的题

更多应用

阮一峰老师的文章里提到了使用异或去做数据备份和加密，感兴趣的同学可以看看。

结语

正如之前提到的，面试题考技巧不是一个好主意。他们需要知道一个晦涩的技巧，一旦知道了这个技巧，就没什么要解决的了（也许对于面试题4来说除外）：几乎没有一种方式可以突显算法思维，也没有好的方式来使用数据结构。

当然，知道怎么去使用异或还是一件很酷的事情的~

参考链接

• 原文链接
• MDN
• 阮一峰老师-异或教程