使用 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]

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

Find the missing number using XOR logic

c++

xor

bit

logical-operators