先导知识：

一个int数据4个字节，一个字节8个比特，所以一个int可以表示32位的数
所有的int类型数据总共有2^32/8=512MB的数据，所有的int类型数据可以表示的位数32*2^32=10^11百亿级别的数。

具体解法图示：

image.png

对于多次出现的数据，用两个bit位表示每个数对应的次数情况，01则表示为只出现1次的数。

leetcode真题之位图法或者位运算

异或 相同是0 不同是1 python计算异或先转换成二进制
python中的负数的表示，反码加1
1.例题1：在一堆数中有一个数出现了1次其他数出现了3次，找出那个只出现1次的数。
思路：采用位运算，整数在计算机中表示为32位，用数组中的每个数与每一位的结果若不为零则计数，此时的计数结果为此位为1的结果，如果对3取余的结果不为0，说明出现一次的数此位也为1，如此可以得到出现一次的数的结果，代码如下:

 def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res=0
        for i in range(32):
            cnt=0
            #每次的移位操作
            bit=1<<i
            for num in nums:
                if num & bit!=0:
                     cnt+=bit&num
            #说明二进制表示的此为1
            if cnt%3!=0:
                res|=bit
        return res - 2 ** 32 if res > 2 ** 31 - 1 else res

2.例题2：
leetcode 645 错误的集合
集合中一个数出现了两次，一个数一次都没出现求这两个数：
之前的数组 和index数组和在一起取异或操作，得到的是要求的这两个数的异或结果。
根据异或结果分组求a b最后判断a b返回的顺序，代码如下:

  def findErrorNums(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # res=[]
        # nums=sorted(nums)
        # dup=-1
        # # mis=len(nums)
        # mis=1
        # for i in range(1,len(nums)+1):
        #     c=nums.count(i)
        #     if c==2:
        #         dup=i
        #     elif c==0:
        # if nums[i]==nums[i-1]:
        #     dup=nums[i]
        # elif nums[i]>nums[i-1]+1:
        #     mis=nums[i-1]+1
        # return [dup,mis]
        #重复的数字
        # n1 = sum(nums)-sum(set(nums))
        # #丢失的数字
        # n2 = sum(range(len(nums)+1))-sum(set(nums))
        # return [n1,n2]
        #位运算方法
        idx=[i+1 for i in range(len(nums))]
        res=idx+nums
        ret=0
        a=0
        b=0
        for item in res:
            ret^=item
        h=1
        while(ret&h==0):
            h<<=1
        for item in res:
            if item&h==0:
                a^=item
            else:
                b^=item
        for j in nums:
            if a==j:
                return [a,b]
        return [b,a]