XOR 如何帮助找到唯一值？

Question

我在编写一个从数组中找到唯一值的函数时遇到问题，我无法解决问题，但我请人帮忙，他使用 XOR(^) 提供了解决方案，但无法解释让我理解它。我知道 XOR 具有以下 table:

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

因此，如果值不同 XOR returns 1 或在其他数字的情况下为非负值，但我仍然不明白这是如何帮助我解决这个问题的。有人可以解释一下下面的代码是如何工作的以及它是如何找到唯一值的吗？

int xor = 0;
int index = 0;
    
while(index < arr.length) {
    xor = arr[index] ^ xor;
    index++;
}
    
return xor;

Answer 1

如果数组的所有元素都可以分组为一对相等的数字，则对每对数字进行异或运算将得到 0。元素异或的顺序无关紧要。

例如数组为4,5,4,5

xor = arr[0] ^ xor; // 0..0100 ^ 0..0000 = 0..0100
xor = arr[1] ^ xor; // 0..0101 ^ 0..0100 = 0..0001
xor = arr[2] ^ xor; // 0..0100 ^ 0..0001 = 0..0101
xor = arr[3] ^ xor; // 0..0101 ^ 0..0101 = 0..0000 = 0

另一方面，如果数组中除一个元素之外的所有元素都可以配对，则在对所有元素进行异或后，将只剩下一个 un-paired 元素。

例如数组为4,5,6,4,5

xor = arr[0] ^ xor; // 0..0100 ^ 0..0000 = 0..0100
xor = arr[1] ^ xor; // 0..0101 ^ 0..0100 = 0..0001
xor = arr[2] ^ xor; // 0..0110 ^ 0..0001 = 0..0111
xor = arr[3] ^ xor; // 0..0100 ^ 0..0111 = 0..0011
xor = arr[4] ^ xor; // 0..0101 ^ 0..0011 = 0..0110 = 6

Answer 2

仅当您具有一个唯一值且重复值的数量为偶数时才有效。

考虑以下测试用例： 7 ^ 3 ^ 5 ^ 4 ^ 5 ^ 3 ^ 4 这可以重新排列为 7 ^ (3 ^ 3) ^ (4 ^ 4) ^ (5 ^ 5)

xor 可交换：A ^ B = B ^ A
xor 是结合的：(A ^ B) ^ C = A ^ (B ^ C)
与零异或什么都不做：A ^ 0 = A
异或两次将其删除：A ^ A = 0

将此规则应用于上述测试用例给出 7 ^ 0 ^ 0 ^ 0 然后 7 ^ 0 即 7

Refer this 了解有关 XOR

的更多信息

XOR 如何帮助找到唯一值？

How is XOR helping find the unique value?

java

arrays

xor