我不明白这个异或发生了什么

Question

我正在处理这个问题。 “给定一个数组，找到出现奇数次的整数。永远只有一个整数出现奇数次。” 我在网上想出了这个解决方案：

function findOdd(A) {
var n = 0;
  for(var i = 0; i < A.length; i++){
  n = n^A[i];
  }

  return n;
}

这行得通，但我不确定为什么，我希望有人能向我解释一下。我只是不明白这行：

n = n^A[i];

你能告诉我在这种情况下它在做什么吗？

Answer 1

任何一个数与其自身异或都会得到0。如果知道只有一个数出现奇数次，其他数就会自异相抵消，答案就是剩下的那个数出现奇数次。

Answer 2

^ 是一个 exor 位运算符。所以当你这样做时

所以要找到 1 的奇数，下面的代码所做的是最初结果是 arr[0] 是 1 。所以在数组中 0^0 变为 0 并且 2^2 变为 0 并且有 3 个 1's 所以 1^1 变为 0 而对于 0^1 我们遗漏了重复奇数次的数字

var arr=[1,1,1,0,0,2,2];
var result=arr[0];
for(var i=1;i<arr.length;i++)
  result=result ^ arr[i];

console.log(result);

希望对您有所帮助

Answer 3

两个相同数字的异或总是零。也就是说，

A^A=0

因此，如果您将一个特定数字与自身重复异或偶数次，结果将为零。

这里，最初n的值为零。将进行偶数次 XOR 运算的数字的结果为零。出现奇数次的数字，比如 2m+1 次，出现 2m 次时结果为零，最后一次出现时结果为相同的数字。

这就是这个解决方案的工作原理。

Answer 4

按位运算符处理 32 位数字。操作中的任何数字操作数都转换为 32 位数字。结果被转换回 JavaScript 数字。 ^ 是按位异或 javascript 运算符。

按位 XOR 运算符 returns 每个位位置的一个 1，其中一个操作数的对应位（但不是两个操作数的对应位都是 1）。

如果 a 和 b 不同，则 a XOR b 产生 1。异或运算的真值table是：

a   b       a XOR b

0   0         0
0   1         1
1   0         1
1   1         0

表达式的解释 n = n^A[i];

让A = [1,2,3,4,5]

for n=0, i=0 => 0 ^ A[0] => 0 ^ 1 => 转换为二进制 0000 ^ 0001 结果为 0001 等于 1

for n=1, i=1 => 1 ^ A[1] => 1 ^ 1 => 转换为二进制 1111 ^ 0010 结果为 1101 等于 13

等等...希望这个解决方案可以帮助您理解上面的表达式并消除所有疑虑。

I don't understand what is happening with this XOR