XOR的结合律逻辑证明

Question

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

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

答案应该是整数5，因为它在列表中出现了3次，而其他整数出现了偶数次。

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

然而，我发现一个更有效的解决方案是简单地对每个元素执行异或操作--甚至不需要排序数组！也就是说：

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

我回忆起我上离散结构课时学到的异或运算具有结合律，并且这就是为什么这个解决方案可行的原因：

a^a = 0

并且：

a^a^a = a

虽然我记得联想律适用于异或运算，但是我很难找到一种特定于异或的逻辑证明（大多数互联网上的逻辑证明似乎更专注于AND和OR操作）。有人知道为什么联想律适用于异或运算吗？

我猜这涉及一个包含AND和/或OR的异或恒等式。

- Vilhelm Gray

---

你只需要考虑一个比特位。XOR 是模 2 加法，并从整数加法继承结合律。或者只需检查函数表。 - Daniel Fischer

无论如何，您可以使用真值表来验证这一点。 - md5

当你有AND和OR的结合律证明时，你可以使用a xor b = ¬((a and b) or (¬a and ¬b))来证明XOR的结合律。 - harold

我不明白为什么异或版本会起作用。如果列表是{1,2,3,4}，那么1^2^3^4 = ? - ylc

@ylc 4，但它是无关紧要的，它解决了“查找出现奇数次的一个整数”的问题，因此包含多个数字奇数次的列表超出了该问题的范围。 - harold

@harold 哦，谢谢指出。是我不好。 - ylc

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) 相同，因此结合律成立。

- Eric Postpischil

Answer 2

只要a ^ b == ~a & b | a & ~b，你就可以证明：

(a ^ b) ^ c = ~((~a & b) | (a & ~b)) & c | ((~a & b) | (a & ~b)) & ~c

并且

a ^ (b ^ c) = a & ~((~b & c) | (b & ~c)) | ~a & ((~b & c) | (b & ~c))

相等。

- md5