先导知识：
一个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]
