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。

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

Answer 1

一些重要的概念：

1. 数字与自身的XOR始终为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

因此，奇数仍然存在。