“^=”运算符在这个查找非配对数字算法中做了什么？

Question

看到一段有趣的代码，用于在重复数字列表中找到一个孤独的数字（其中列表中的每个数字都出现两次，除了一个）。

function findNonPaired(listOfNumbers) {
  let nonPairedNumber = 0

  listOfNumbers.forEach((n) => {
      nonPairedNumber ^= n
  })

  return nonPairedNumber
}

const x = [1,5,4,3,9,2,3,1,4,5,9]
console.log(findNonPaired(x))

这个解决方案看起来非常优雅，但我很好奇 ^= 运算符实际上在这里做什么？

Answer 1

a ^= b 与 a = a ^ b 相同，其中 ^ 是按位异或运算符。

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

这是一个巧妙的算法。让我们用列表 [8, 12, 8] 跟踪一次执行，例如：

0 ^ 8 = 0000 ^ 1000 = 1000
        1000 ^ 1100 = 0100
        0100 ^ 1000 = 1100 = 12

单词"duplicate"不正确。该算法测试奇偶校验。一个简单但有些错误的定义是 "when everything has a pair"。对...平价。

[2,2,2,3,3,5,5,5,5] 会 return 2 因为其他所有东西都有一对。

[3,4,5] 实际上会 return 2 (011^100^101 -> 010) 因为这是所有未配对项目的异或。

Answer 2

就像其他答案所说的那样 - 它是按位异或。

关于算法 - 如果您确定重复项是偶数，那就太好了。当一个数字与 x 进行异或运算，然后再次与 x 进行异或运算时，它将 return 为其先前的值。如果一个数字在此链中出现 3 次，则第 3 次出现将欺骗此算法。此外，如果链中还有一个单独的值，例如：

a, b, c, X, a, c, b, Y

结果将是 (X ^ Y)，您无法确定是否有一个或多个唯一值。

“^=”运算符在这个查找非配对数字算法中做了什么？

What does the "^=" operator do in this find non-paired number algorithm?

javascript

bit-manipulation

bitwise-operators