c - 异或结合属性的逻辑证明

Question

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

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

解决方案是整数 5，因为它在列表中出现了 3 次，而其他整数出现了偶数次。

我最初的解决方案涉及设置一个排序数组，然后遍历数组:对于每个奇数元素，我将添加整数，而对于每个偶数元素，我将减去；最终总和是解决方案，因为其他整数会抵消。

但是，我发现存在一种更有效的解决方案，只需对每个元素执行异或操作——您甚至不需要排序数组!也就是说:

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

我记得在一个离散结构类中，关联属性适用于 XOR 运算，这就是这个解决方案有效的原因:

a^a = 0

和:

a^a^a = a

虽然我记得关联属性适用于 XOR，但我很难找到 XOR 特定的此属性的逻辑证明(Internet 上的大多数逻辑证明似乎更侧重于 AND 和 OR 操作)。有谁知道为什么 Associative Property 适用于 XOR 运算？

我怀疑它涉及包含 AND 和/或 OR 的异或标识。

Answer 1

关联属性表示 (a^b)^c = a^(b^c)。由于异或是按位的(数字中的位被并行处理)，我们只需要考虑单个位的异或。然后可以通过检查所有可能性来完成证明:

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) 相同，因此关联属性成立。