使用 XOR 逻辑查找缺失的数字

Question

给定一个大小为 N-1 的数组 C，并且给定从 1 到 N 的数字缺少一个元素，则可以找到缺少的数字。

我已经看到它可以使用XOR的一些有趣的属性来解决。

有趣的属性是

Assume a1 ^ a2 ^ a3 ^ …^ an = x and a1 ^ a2 ^ a3 ^ …^ an-1 = y
Then x ^ y = an

我试图理解逻辑，但我失败了。

有人可以解释其中涉及的逻辑吗？

Answer 1

根据定义，a ^ a是0，在您的情况下，您正在计算：

x: a[0] ^ a[1] ^ a[2] ^ .. ^ a[n-1] ^ a[n] ^
y: a[0] ^ a[1] ^ a[2] ^ .. ^ a[n-1]        
=======================================
0 ^    0 ^    0 ^ .. ^      0 ^ a[n] = a[n]