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

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

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

我最初的解决方案是建立一个排序后的数组,然后遍历该数组:对于每个奇数元素,我将添加整数,而对于每个偶数元素,我将减去;最终的和是解决方案,因为其他整数将被抵消。

但是,我发现,只需对每个元素执行XOR,就可以找到更有效的解决方案-您甚至不需要排序数组!也就是说:
2^3^5^2^5^5^3 = 5

我从一个离散结构类中记忆起,我认为关联属性适用于XOR操作,这就是该解决方案起作用的原因:
a^a = 0

和:
a^a^a = a

尽管我记得关联属性适用于XOR,但我很难找到针对该属性的逻辑证明(特定于XOR)(Internet上的大多数逻辑证明似乎都集中在AND和OR运算上)。有谁知道为什么关联属性适用于XOR操作?

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

最佳答案

关联属性表示(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)相同,所以保留了关联属性。

09-10 11:26
查看更多