缺失
class Solution:
def missingNumber(self, nums: List[int]) -> int:
curr = 0
for i in range(len(nums)+1):
curr ^= i
for i in nums:
curr ^= i
return curr
ps：跟位运算无关但跟“缺失”有关的题目：
只出现一次的数字
class Solution:
def singleNumber(self, nums: List[int]) -> int:
curr = 0
for n in nums:
curr ^= n
return curr
- 一定要记得a，b轮流更新时用的a，b是旧的还是新的
- 题解区的卡诺图你还记得吗
class Solution:
def singleNumber(self, nums: List[int]) -> int:
a, b = 0, 0
for n in nums:
b = (b ^ n) & ~a
a = (a ^ n) & ~b
return b
- 分组思想
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
# div = n1 ^ n2
div = 0
for n in nums:
div ^= n
# find the lowest bit where n1 != n2
h = 1
while div & h == 0:
h <<= 1
# get n1 and n2
a, b = 0, 0
for n in nums:
if n & h == 0:
a ^= n
else:
b ^= n
return [a, b]
二进制子集
- 二进制子集遍历方法：while循环，subset = (subset-1)&fullset。
subset = fullset
while subset:
......
subset = (subset-1) & fullset
338. 比特位计数
核心就在于如何找到一个更小的数，发现两者之间的规律。
有三种动态规划的方法：最低有效位/最高有效位/最高设置位（1位）
几个规律：
正整数 y 是 2 的整数次幂，当且仅当y&(y-1)=0。
y=x&(x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数。
