为什么 Bitwise XOR ( ^ ) 给出的示例结果不同？这是什么逻辑？ JS

Question

给出一个由N个整数组成的非空数组A。该数组包含奇数个元素，并且数组的每个元素都可以与另一个具有相同值的元素配对，除了一个未配对的元素。

例如，在数组 A 中：

A[0] = 9  A[1] = 3  A[2] = 9
A[3] = 3  A[4] = 9  A[5] = 7
A[6] = 9

索引 0 和 2 的元素值为 9，索引 1 和 3 处的元素的值为 3，索引 4 和 6 处的元素的值为 9，索引 5 处的元素的值为 7 且未配对。写一个函数：

function solution(A);

给定一个由满足上述条件的 N 个整数组成的数组 A，returns 是不成对元素的值。

例如，给定数组 A 使得：

 A[0] = 9  A[1] = 3  A[2] = 9
 A[3] = 3  A[4] = 9  A[5] = 7
 A[6] = 9

函数应 return 7，如上例所述。

function different(a) {
  let result = 0;

    for (let element of a) {
        result ^= element
    }

  return result;
}

const arr = [9, 3, 9, 3, 9, 7, 9];

我发现这个解决方案非常适合所需的条件。我不明白按位异或 ( ^ )

我还测试了不同的数组；

 arr = [9, 3, 9, 3, 9, 7, 9];  //returns 7 
 arr = [9];                    //returns 9
 arr = [9, 3];                 //returns 10
 arr = [9, 3, 9, 3];           //returns 0
 arr = [9, 3, 9, 9 ];          //returns 10
 arr = [9, 3, 9, 2 ];          //returns 2

谁能向我解释一下它是如何工作的？其背后的逻辑是什么？为什么它只在要求的条件下才能完美运行？

Answer 1

此代码有效，因为当您 XOR 一个带有 0 的数字时，您会得到该数字，而当您 XOR 一个带有自身的数字时，您会得到 0 .对于只有一个未配对数字 ([9, 3, 9, 3, 9, 7, 9]) 的数组的特定条件，您可以将循环展开为

result = 0 ^ 9 ^ 3 ^ 9 ^ 3 ^ 9 ^ 7 ^ 9

自从

a ^ b = b ^ a

这可以改写为

result = 0 ^ 9 ^ 9 ^ 3 ^ 3 ^ 7 ^ 9 ^ 9
       = 0 ^ 0 ^ 0 ^ 7 ^ 0
       = 7

当存在多个不匹配值时，此方法不起作用的原因是您最终得到的结果是所有不匹配值的 XOR。例如，对于 [9, 3, 9, 9] 你得到

result = 9 ^ 3 ^ 9 ^ 9
       = 9 ^ 3 ^ 0
       = 10

Answer 2

在回答主要问题之前，您应该了解 XOR 的工作原理。对于偶数个相同的位，xor 的位为 0，对于奇数个位，xor 的位为 1。 XOR 的真值table- 异或 0 0 0 0 1 1 1 0 1 1 1 0

现在开始你的推理：

假设你想异或，注意中间状态是二进制表示

2^2 = 10 ^ 10 = 00 = 0（以 10 为基数）
2^2^3 = 10^10^11 = 11 = 3（以 10 为基数）
1^2^3 = 01^10^11 = 00 = 0（以 10 为基数）

注意到错误的结果了吗？我希望现在您知道 XOR 是如何工作的。所以只有当数字在数组中配对时它才会起作用，并且只会正确地找出一个未配对的数字。

为什么 Bitwise XOR ( ^ ) 给出的示例结果不同？这是什么逻辑？ JS

Why do Bitwise XOR ( ^ ) given example results differ? What is the logic? JS

javascript

arrays

bitwise-xor