数组中只出现一次的数字

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

这道题如果没有想到用异或来解决的话，可能就比较不容易做出来了。异或操作有一个好处在于，两个相同的数异或的结果是0，并且异或操作是满足交换率的，所以异或的顺序对结果不会有影响。
想到这一点的话，就可以知道，我们首先遍历一遍整个数组，得到所有数字的异或结果，这个结果相当于是两个只出现一次的数字的异或结果，并且这个结果一定不是0（因为这两个数不一样）。

假设这个异或的结果中，第k位为1，我们根据第k位是不是1为标准，把原数组分成两个子数组，一个子数组中每个数字的第k位都是1，另一个子子数组中每个数字的第k位都是0，这样，两个只出现一次的数分别被分到不同的子数组中，并且每对相同的数字都会被分配到同一个子数组中。

针对每一个子数组，再利用异或的方法，即可找到那个只出现一次的数字。

#encoding=utf8
'''
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
要求时间复杂度是O(n)，空间复杂度是O(1)。
'''
 
def find_two_unique_num(num_list):
    result = 0
    for num in num_list:
        result ^= num
    lowbit = find_lowest_bit(result)
    result_1 = 0
    result_2 = 0
    for num in num_list:
        if num & lowbit != 0:
            result_1 ^= num
        else:
            result_2 ^= num
    return (result_1, result_2)
 
def find_lowest_bit(num):
    index = 0
    while num & 1 == 0:
        num = num >> 1
        index  = 1
    return 1 << index
    
if __name__ == '__main__':
    num_list_1 = [2, 2, 1, 3]
    num_list_2 = [2, 4, 3, 6, 3, 2, 5, 5]
    print find_two_unique_num(num_list_1)
    print find_two_unique_num(num_list_2)