2019-08-21剑指 数组中只出现一次的数字

50min。对二进制位的处理，分治的思想。
1.花的时间最长的反而是如何求一个数的二进制位数，反而有现成函数，log函数的使用
2.异或的交换律，结合律

# -*- coding:utf-8 -*-
from functools import reduce
import math
from typing import List
class Solution:
    def FindNumsAppearOnce(self, array):
        result=reduce(lambda x,y:x^y,array)
        first_digit=self.get_first_digit(result)
        l1=[]
        l2=[]
        for n in array:
            if n&(1<<(first_digit-1))==0:l1.append(n)
            else:l2.append(n)
        return [reduce(lambda x,y:x^y,l1),reduce(lambda x,y:x^y,l2)]


    def get_first_digit(self,num:int):
        if num==0:return 0
        # length=math.floor(math.log(num,2))+1 if num!=0 else 1# 位数要搞清楚，这里要1
        length=num.bit_length()
        for i in range(int(length)):
            tmp=num&(1<<i) # 每个数位数不同所以从求最低位，其实可以把数右移更简单
            if tmp!=0:return i+1


if __name__ == '__main__':
    t=Solution()
    print(t.FindNumsAppearOnce([1,2,1,2,4,5]))
    print(t.FindNumsAppearOnce([1,3,1,4,4,5]))
    # print(t.get_first_digit(1))
    # print(t.get_first_digit(0))
    # print(t.get_first_digit(2))
    # print(t.get_first_digit(3))
    # print(t.get_first_digit(4))