我遇到了一个常见的编程访谈问题:给定一个无符号整数的列表,找到一个整数,该整数发生在列表中的奇数次数。例如,如果给出列表:
{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上的大多数逻辑证明似乎更专注于和和/或操作)。有人知道为什么关联属性适用于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)
,关联属性保存。
只要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))
是平等的。