# coding: utf8

'''
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

时间复杂度 O(n)

空间复杂度 O(1)
'''

# 解题思路:
# 如果数组中只有一个数出现一次, 其它数均出现两次, 那么可以直接使用异或运算求出单数, 因为重复的数在异或运算下为 0
# 有了这个思路后我们可以想将数组分为两堆, 每堆里含有一个单数, 其它若干个重复数, 这样就可以分别求出出现一次的数
# 我们从头到尾异或整个数组, 剩下的结果为两个只出现一次的数的异或结果. 因为其他数字都出现了两次，在异或中全部抵消掉了。
# 由于这两个数字肯定不相等, 所以这个结果必不为 0, 至少这个结果中的二进制表示中至少就有一位为 1
# 我们在这个结果中找到第一位为 1 位的位置,记作第 N 位, 比如: 4 = 100, 则 N = 2
# 现在我们以第 N 位是否为 1 的标准把原数组中的数字分成两个子数组, 由于数字相同肯定会分到同一个子数组里面, 所以到最后这些肯定都会相互抵消掉
# 第一个子数组中每一个数字的第 N 位都为 1, 而第二个数组中每一个数字的第 N 位都为 0
# 现在已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题都已经解决。



# 找到一个数的二进制表示中从右往左第一个出现 1 的数
def find_low_bit(num):
    index = 0
    while ((num & 1) == 0) and (index < 32):
        num = num >> 1
        index += 1
    return index

# 确认某个数在二进制表示下从右往左第 index 位的数是否为 1
def find_index_is_1(num, index):
    num = num >> index
    return (num & 1) != 0


# 主函数:
def find_two_numbers(arr):
    num = 0
    for i in range(0, len(arr)):
        num ^= arr[i]
    index = find_low_bit(num)
    num1 = 0
    num2 = 0
    for j in range(0, len(arr)):
        if find_index_is_1(arr[j], index):
            num1 ^= arr[j]
        else:
            num2 ^= arr[j]

    return (num1, num2)


if __name__ == '__main__':
    print(find_two_numbers([1, 2, 3, 4, 5, 6, 1, 3, 4, 6]))






