python - XOR 查找两个列表之间的缺失元素

Question

我试图解决这个问题

“考虑一个非负整数数组。第二个数组是通过将第一个数组的元素打乱并删除一个随机元素形成的。给定这两个数组，找出第二个数组中缺少哪个元素。”

解决方案之一是使用 XOR 的代码

def find(arr1, arr2): 
    result=0 

    # Perform an XOR between the numbers in the arrays
    for num in arr1+arr2: 
        result^=num 
        print result

    return result 


arr1 = [1,2,3,4,5,6,7]

arr2 = [3,7,2,1,4,6]

函数的结果是 5。

我知道异或的基本原理。但是我不明白上面的代码是如何找到结果的。

Answer 1

一些重要的概念：

1. 一个数与自身的异或总是 0

2. 数字与 0 的 XOR 始终是数字本身

3. XOR 操作的顺序无关紧要

有了这个，考虑：

1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 3 ^ 7 ^ 2 ^ 1 ^ 4 ^ 6

→ (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4) ^ (5) ^ (6 ^ 6) ^ (7 ^ 7)

→  0   ^     0   ^     0   ^      0   ^  5  ^     0   ^   0

→  5

所以，奇怪的一个仍然存在。

Answer 2

你从结果开始 = 0

然后你继续用每个数组的所有元素对结果进行异或运算。XOR 翻转您当前拥有的数字的所有非零位。

因此，当您两次遇到相同的数字时，您已经两次翻转了同一组位 - 这意味着您回到了开始的状态。

两个列表中出现的每个数字最终都会“取消自身”。唯一未取消的数字是第二个列表中缺少的数字。

每个整数是什么都没关系 - 如果数字出现两次，位将翻转两次，如果数字出现一次，则翻转一次。第一个或第二个数组中是否缺少数字甚至都没有关系。