通过 XOR 解决丢失序列号问题
我试图了解 XOR 操作如何设法解决问题 PermMissingElem< /a>
我知道 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
I'm trying to understand how the XOR operation managed to solve the problem PermMissingElem
I know one of the properties of XOR is that:
A ⊕ B = C
C ⊕ A = B
C ⊕ B = A
>>> 3 ^ 4
7
>>> 7 ^ 3
4
This can be repeated for any number of operations, in this case it was 2 numbers, but it could be 3, 4, 5... n
Another property is that:
A ⊕ A = 0
A ⊕ 0 = A
>>> 3 ^ 3
0
>>> 3 ^ 0
3
But looking at the problem PermMissingElem
how was it possible to guarantee that the last operation would be exactly the number that was missing? Is there any literature on this algorithm, has anyone talked about it?
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)
out
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
as can be seen:
11 ⊕ 7 ⊕ 6 = 10
7 ⊕ 11 ⊕ 10 = 6
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您知道，输入范围
[1..n+1]中的每个数字都恰好有一个，除了缺少一个k以及a ⊕ a = 0，如果你有另一个数组
[1..n+1]，并且没有丢失k，那么，在合并这些数组时，我们将有一个大数组，其中每个数字重复两次，除了
k。因此，如果我们对该数组的所有元素进行异或，则每个重复的元素都会自行取消，我们将留下k，这是您丢失的数字。Since you know, there is exactly one of each number in the input in range
[1..n+1]except for one missingkand the fact thata ⊕ a = 0,if you have another array
[1..n+1], without missingk,then, on merging these arrays, we will have one big array with every number repeated twice, except
k. So, if we XOR all elements of this array, each repeated element cancels itself and we will be left withk, which is your missing number.XOR 运算是可交换的，应用的顺序并不重要。
具有相同值的两个 XOR 会相互抵消。
因此，从 0 开始并应用任意 XOR 序列，然后是包含额外元素的相同序列，则仅保留额外元素的效果。
例如 0 ⊕2⊕3⊕1⊕5 ⊕1⊕2⊕3⊕4⊕5 与 0⊕1⊕1⊕2⊕2⊕3⊕3⊕4⊕5⊕5 或 0⊕4 具有相同的效果。
The XOR operation is commutative, the order of application does not matter.
Two XORs with the same value cancel each other.
So, starting from 0 and applying any sequence of XORs, followed by the same sequence that includes an extra element, only the effect of the extra element remains.
E.g. 0 ⊕2⊕3⊕1⊕5 ⊕1⊕2⊕3⊕4⊕5 has the same effect as 0⊕1⊕1⊕2⊕2⊕3⊕3⊕4⊕5⊕5, or 0⊕4.