題目：一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。

這道題如果沒有想到用異或來解決的話，可能就比較不容易做出來了。異或操作有一個好處在于，兩個相同的數(shù)異或的結(jié)果是0，并且異或操作是滿足交換率的，所以異或的順序?qū)Y(jié)果不會有影響。
想到這一點的話，就可以知道，我們首先遍歷一遍整個數(shù)組，得到所有數(shù)字的異或結(jié)果，這個結(jié)果相當(dāng)于是兩個只出現(xiàn)一次的數(shù)字的異或結(jié)果，并且這個結(jié)果一定不是0（因為這兩個數(shù)不一樣）。

假設(shè)這個異或的結(jié)果中，第k位為1，我們根據(jù)第k位是不是1為標(biāo)準(zhǔn)，把原數(shù)組分成兩個子數(shù)組，一個子數(shù)組中每個數(shù)字的第k位都是1，另一個子子數(shù)組中每個數(shù)字的第k位都是0，這樣，兩個只出現(xiàn)一次的數(shù)分別被分到不同的子數(shù)組中，并且每對相同的數(shù)字都會被分配到同一個子數(shù)組中。

針對每一個子數(shù)組，再利用異或的方法，即可找到那個只出現(xiàn)一次的數(shù)字。

#encoding=utf8
'''
題目：一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。
要求時間復(fù)雜度是O(n)，空間復(fù)雜度是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)