XOR 运算仅返回整数数组中的非对元素

Question

我在解决 Hackerrank 上的挑战时遇到了这个问题。

\n\n

/*\nProblem Statement\n\nThere are N integers in an array A. All but one integer occur in pairs. Your task is to find the number that occurs only once.\n\nInput Format\n\nThe first line of the input contains an integer N, indicating the number of integers. The next line contains N space-separated integers that form the array A.\n\nConstraints\n\n1\xe2\x89\xa4N<100 \nN % 2=1 (N is an odd number) \n0\xe2\x89\xa4A[i]\xe2\x89\xa4100,\xe2\x88\x80i\xe2\x88\x88[1,N]\nOutput Format\n\nOutput S, the number that occurs only once.\n*/\n

\n\n

我在这种情况下编写的正常解决方案结果非常复杂，有很多嵌套的 if 循环。经过一番搜索，我发现这个解决方案通过简单地将整数数组中的所有元素相互异或来解决问题，结果是孤独的整数。

\n\n

这是相关方法（main() 方法接受输入并将其解析为整数数组，未显示，因为它与此处不相关）：

\n\n

    static int lonelyinteger(int[] a) {\n\n        int n = a.length;\n        int result = 0;\n        for( int i = 0; i < n; i++) {\n            result = result ^ a[i];\n        }\n\n        return  result;\n\n}\n

\n\n

我不确定这个 XOR 运算如何能够返回数组中的“孤独整数”。我知道 XOR 的两个属性：

\n\n

 1. a^a=0\n 2. a^0=a\n

\n\n

但除此之外，我不太清楚 XOR 在这里是如何工作的。

\n\n

SO 上还有另一个问题，内容相同，但提出了不同的问题，所以我不得不（再次）问这个问题。

\n\n

如果有人能为这个 XOR 操作提供详细的解释，我将不胜感激。

\n

Answer 1

由于a^a对于任何 等于 0 a，所有匹配的整数对将相互抵消，留下 0。然后将其与最终数字进行异或。由于对于任何0^a等于，结果将是最终的数字。简单演示：aa

$ ruby -e 'puts [1,1,2,2,3,3,4,5,5,6,6].reduce :^'
4

如果你仔细查看各个对，你就会明白为什么这是有效的：

1 ^ 1 = 0 
0 ^ 2 = 2
2 ^ 2 = 0
0 ^ 3 = 3
3 ^ 3 = 0
0 ^ 4 = 4
4 ^ 5 = 1
1 ^ 5 = 4
4 ^ 6 = 2
2 ^ 6 = 4

结果在 0 和最新数字之间切换，直到找到孤独者；之后，它会在该数字和...与最新数字进行异或时得到的任何内容之间切换。那里的实际值并不重要，因为当您对该数字的第二个副本进行异或时，它会被修改，并且您将返回到单例的副本。

我对数字进行了排序，以便轻松发现单例，但由于 XOR 会自行撤销，因此顺序根本不重要：

$ ruby -e 'puts [6,3,4,1,1,2,2,6,3,5,5].reduce :^'
4

6 ^ 3 是...某个数字，然后该数字 ^ 4 是其他数字，然后将其与 1 进行异或，这些都不重要，因为然后您撤消 1，然后使用另一个中间结果2 并立即撤消它，然后撤消 6 和 3，这样您就回到了 4。您将其与 5 进行异或以获得另一个临时数字，然后该数字被最后的 5 冲走，留下，再说一次，4。