JAVA - 在给定的解决方案中，按位异或赋值运算符如何工作

Question

我最近在做一些编程挑战，其中之一就是这个问题。

给定一个非空的零索引数组A，由N个整数组成。该数组包含奇数个元素，数组中的每个元素都可以与另一个具有相同值的元素配对，除了一个未配对的元素。找到未配对的值。例如，给定数组A：A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9，函数应返回7。

完成我的代码后，我发现了这个解决方案。

public int solution(int[] A) {
  int r = 0;
  for(int i=0;i<A.length;i++)
    r ^=A[i];

  return r;
}

我对这段代码感到惊讶。我从未见过异或赋值运算符，并想知道这个解决方案是如何工作的。如果有人能为我讲解一下这个简单的代码并解释它的工作原理，那就太棒了。

- Bryan Mcneil

---

提示：(1)异或是可交换的。(2)异或是可结合的。(3)任何整数与自身进行异或运算的结果都是零。 - Dawood ibn Kareem

r ^=A[i]; 和 r = r ^ A[i]; 是相同的。你对这段代码片段还有什么不理解的吗？ - Erwin Bolwidt

Answer 1

简而言之，A ^ B ^ B 将会返回 A。这两个^B并不需要连续出现：只要XOR同一个值两次，就可以清除其影响。在你的问题中，因为数值成对出现，所以同一个值通常会被XOR两次，在最终的计算结果中没有影响，除非是那些没有配对的值。因此最终结果将会是0 ^ 那个未配对的值，即那个未配对的值。

- Adrian Shum

Answer 2

在二进制系统中，两个相同的数字进行异或运算（用符号^表示）的结果为零。

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

同样的规则适用于任何系统，在你的例子中，数字 9 的二进制表示为1001，因此数字 9 和 9 的异或运算符^结果为

 1001
 1001
 ----
 0000
 ----

在你的例子中，(9^9)^(9^9)得到零，(3^3)得到零，最后剩下0^7，即7。

- user8885515