用 XOR 解决序列号缺失问题

Question

我正在尝试了解 XOR 运算如何设法解决问题 PermMissingElem

我知道 XOR 的特性之一是：

A ⊕ B = C
C ⊕ A = B
C ⊕ B = A

>>> 3 ^ 4
7
>>> 7 ^ 3
4

这可以重复任意数量的操作，在本例中是 2 个数字，但也可以是 3、4、5...n

另一个属性是：

A ⊕ A = 0
A ⊕ 0 = A

>>> 3 ^ 3
0
>>> 3 ^ 0
3

但是看问题PermMissingElem 怎么可能保证最后一次操作就是丢失的数字呢？有没有关于这个算法的文献，有人讲过吗？

A = [1,2,3,4,5,7,8,9,10,11]

missing_element = len(A)+1

for idx,value in enumerate(A):

    print(missing_element, value, (idx+1), ' = ', missing_element ^ value ^ (idx+1))
    missing_element = missing_element ^ value ^ (idx+1)

出来

11 1 1  =  11
11 2 2  =  11
11 3 3  =  11
11 4 4  =  11
11 5 5  =  11
> 11 7 6  =  10
10 8 7  =  5
5  9 8  =  4
4 10 9  =  7
> 7 11 10 =  6

可以看出：

11 ⊕ 7 ⊕ 6 = 10
7 ⊕ 11 ⊕ 10 = 6

Answer 1

异或运算是可交换的，应用顺序无关紧要。

具有相同值的两个异或相互抵消。

因此，从 0 开始并应用任何异或序列，然后是包含额外元素的相同序列，只保留额外元素的效果。

例如0 ⊕2⊕3⊕1⊕5 ⊕1⊕2⊕3⊕4⊕5 与 0⊕1⊕1⊕2⊕2⊕3⊕3⊕4⊕5⊕5 或 0⊕4 具有相同的效果。

Answer 2

既然你知道，输入范围 [1..n+1] 中的每个数字都恰好有一个，除了缺少一个 k 以及 a ⊕ a = 0、

这一事实

如果你有另一个数组[1..n+1]，没有遗漏k，

然后，在合并这些数组时，我们将得到一个大数组，每个数字重复两次，除了 k。所以，如果我们对这个数组的所有元素进行异或运算，每个重复的元素都会自行取消，我们将留下 k，这是您缺少的数字。

用 XOR 解决序列号缺失问题

Missing sequence number problem solved with XOR

algorithm

binary

xor