异或的关联性质的逻辑证明

Question

我遇到了一个常见的编程访谈问题:给定一个无符号整数列表,找到一个在列表中出现奇数次的整数.例如,如果给出列表:

{2,3,5,2,5,5,3}

解决方案将是整数5,因为它在列表中出现3次而其他整数出现偶数次.

我的原始解决方案包括设置一个排序数组,然后迭代数组:对于每个奇数元素,我会添加整数,而对于每个偶数元素,我会减去; 结束总和是解决方案,因为其他整数将取消.

但是,我发现只需在每个元素上执行XOR就可以实现更高效的解决方案 - 您甚至不需要排序数组!也就是说:

2^3^5^2^5^5^3 = 5

我从Discrete Structures类回忆起,我认为Associate Property适用于XOR操作,这就是为什么这个解决方案有效:

a^a = 0

和:

a^a^a = a

虽然我记得Associative Property适用于XOR,但是我很难找到特定于XOR的这个属性的逻辑证明(因特网上的大多数逻辑证据似乎更侧重于AND和OR操作).有谁知道为什么关联属性适用于XOR操作？

我怀疑它涉及包含AND和/或OR的XOR身份.

Answer 1

关联属性说明了这一点(a^b)^c = a^(b^c).由于XOR是按位的(数字中的位是并行处理的),我们只需要考虑单个位的XOR.然后可以通过检查所有可能性来完成证明:

abc (a^b) (a^b)^c (b^c) a^(b^c)
000   0      0      0      0
001   0      1      1      1
010   1      1      1      1
011   1      0      0      0
100   1      1      0      1
101   1      0      1      0
110   0      0      1      0
111   0      1      0      1

由于第三列(a^b)^c与第五列相同a^(b^c),因此关联属性成立.