使用 XOR 在 Python 中查找数组中缺失的数字

Question

以下代码运行良好，并使用 XOR 查找连续数组的缺失数。请问为什么第一个循环从1开始到n结束，第二个从2开始到n+2结束？

a = [1, 2, 3,4, 5, 6,8] 
n = len(a)
x1 = a[0]
x2 = 1
for i in range(1, n):
 ##   print (i)
#print (' ')
for i in range(1, n): 
        x1 = x1 ^ a[i]
        print (a[i],x1)
print (' ')
for i in range(2, n + 2): 
        x2 = x2 ^ i 
    ##    print (i,x2)
##print (' ')
print (x1 ^ x2 )

Answer 1

范围不从 0 开始的事实是由于您将 x1 和 x2 初始化为数组的第一个值。

您可以从 0 开始，使用 x1, x2 = 0，就像这样：

a = [1, 2, 3, 4, 5, 6, 8]
n = len(a)
x1 = 0
x2 = 0
for i in range(0, n):
    x1 = x1 ^ a[i]
for i in range(0, n + 2):
    x2 = x2 ^ i
print(x1 ^ x2) # still prints 7

你一直走到 n+2 的事实（实际上只是到 n+1 因为结尾不包括在内）是因为数组缺少元素，所以在你的情况下n+1 是 8，如果不将其与 x2 进行异或运算，您最终会得到错误的值（在本例中，15，即 7^8） .

澄清一下：您必须对实际值与预期值进行异或运算，才能找到缺失的值。

第一个范围包含所有实际值，而第二个范围包含所有可能值，最多 n+1.

使用 XOR 在 Python 中查找数组中缺失的数字

Finding the missing number in array in Python using XOR

python

arrays

xor

series