python - 异或查找两个列表之间缺少的元素

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 的异或总是数字本身

3. 异或运算的顺序无关紧要

有了这个，考虑:

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

因此，剩下的是奇数。