一日一技：使用异或寻找两个孤独的数
摄影：产品经理
公司的团建
两年前，我曾经写过一篇文章：一日一技：使用异或寻找孤独的数，当时，在一个列表里面，只有一个数字只出现一次，所以一轮异或就能解决问题。
现在我们把这个问题难度增加一下：
一个列表里面，有两个孤独的数，这两个数互相不相等。除了他们外，其他的数都成对出现。问如何快速找到这两个数且空间复杂度为 O(1)？
假设给出一个列表：
target = [1, 1, 2, 2, 6, 8, 8, 12, 24, 24]
我们试着再用一下原来的方法，看看得到的是什么：
最后得到的结果是数字10，显然，它是6 xor 12的结果。现在问题来了，已知两个数他们异或以后的结果是10，如果把这两个数分开？
可以明确告诉大家，如果已知条件仅仅是已知c 是两个数的异或值，求这两个数。这个问题有无数的解。但如果再加一个限定条件：且这两个数是某个列表中的两个元素，那么结果就很好确认了。
但问题是，难道你要把原来输入的列表元素两两异或，从而找到这两个值？既然如此，为什么你不直接对列表里面的元素进行计数从而找到两个孤独的数呢？显然两两异或的计算量远远大于直接对列表中的每个元素进行计数。
我们回到异或这个操作本身：两个数字的异或值，等于他们对应的二进制数逐位异或，相同的位值为0，不同的位值为1.
我们来看10的二进制数为1010，那么可以确定的是，如果有两个数他们异或的值是10，那么这两个数对应的二进制数，从右数数第2位一定不相同。
有了这个条件以后，我们只要把原来列表里面的数分成两组：第一组，每个数字的二进制数对应的右数第2位为0；第二组，每个数字的二进制数右数第2位为1。那么，一定可以把这两个孤独的数分开。由于相同的数字，他们的二进制数的右数第二位一定是相同的，所以相同的数一定在同一组。每一组就只有一个孤独的数了。对每一组所有的元素再全部异或一次，就能成功把两个孤独的数识别出来。
根据以上的逻辑，我们可以实现如下代码：
from functools import reduce
def calc_xor(x, y):
return x ^ y
def find_the_most_right_bit_1(num):
"""
寻找数字 num 对应的二进制数里面，最右侧的1所在的位置
例如对于二进制数10110100,只有当它与100做与运算时，返回
的值才会是100本身
"""
if num == 0:
return 0
check_bit = 1
while True:
if num & check_bit == check_bit:
return check_bit
check_bit = check_bit << 1
def find_two_unique_num(target):
if not target:
raise Exception('输入的列表为空')
xor_of_two = reduce(calc_xor, target)
check_bit = find_the_most_right_bit_1(xor_of_two)
group_1 = []
group_2 = []
for num in target:
if num & check_bit == check_bit:
group_1.append(num)
else:
group_2.append(num)
unique_num_1 = reduce(calc_xor, group_1) # 不用担心 group_1只有一个元素的问题，不会报错，reduce能正常处理
unique_num_2 = reduce(calc_xor, group_2)
return unique_num_1, unique_num_2
运行效果如下图所示：
对代码中的部分稍稍解释一下：
reduce(func, [a, b, c, d])等价于：
result = func(a, b)
result = func(result, c)
result = func(result, d)
find_the_most_right_bit_1用于寻找数字 num 对应的二进制数里面，最右侧的1所在的位置，例如对于二进制数10110100，一开始 check_bit为1，两数相与，结果为0。然后1 << 1为二进制10，跟10110100 & 10 != 10，再左移一位，10 << 1 == 100。此时10110100 & 100 == 100于是返回。