LeetCode-191 二进制位1的个数
观察一下 n 与 n-1 这两个数的二进制表示：对于 n-1 这个数的二进制来说，相对于 n 的二进制，它的最末位的一个 1 会变成 0，最末位一个 1 之后的 0 会全部变成 1，其它位相同不变。
所以可以通过执行 n&(n-1) 操作来消除 n 末尾的 1 ，消除了多少次，就说明有多少个 1 。
class Solution:
def hammingWeight(self, n):
res = 0
while n != 0:
res += 1
n &= (n - 1)
return res
def hammingWeight2(self, n):
res = 0
while n != 0:
res += (n & 1)
n = n >> 1
return res
LeetCode-231 2的幂
仔细观察，可以看出 2 的次方数都只有一个 1 ，剩下的都是 0 。根据这个特点，只需要每次判断最低位是否为 1 ，然后向右移位，最后统计 1 的个数即可判断是否是 2 的次方数, 可以使用上一个问题的解法
def isPowerOfTwo(n):
res = 0
while n != 0:
res += (n & 1)
n >>= 1
return res == 1
该题还有一种巧妙的解法。再观察上面的表格，如果一个数是 2 的次方数的话，那么它的二进数必然是最高位为1，其它都为 0 ，那么如果此时我们减 1 的话，则最高位会降一位，其余为 0 的位现在都为变为 1，那么我们把两数相与，就会得到 0.
比如 2 的 3 次方为 8，二进制位 1000 ，那么 8 - 1 = 7，其中 7 的二进制位 0111
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return (n > 0) and ((n & (n - 1)) == 0)
LeetCode-201. 闭区间范围内数字按位与
所有这些位字符串的公共前缀也是指定范围的起始和结束编号的公共前缀（即在上面的示例中分别为 9 和 12）,因此，我们可以将问题重新表述为：给定两个整数，要求我们找到她们二进制字符串的公共前缀
- 使用191的方法
Brian Kernighan 算法n & (n-1)
class Solution:
def rangeBitwiseAnd(self, m: int, n: int) -> int:
while m < n:
# turn off rightmost 1-bit
n = n & (n - 1)
return m & n
- 找m, n 的最高位1出现的位置 ， 如果不相等，则返回0，如果相等，则找公共前缀。B站视频-位运算练习【LeetCode】
LeetCode-187.重复的DNA序列
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]
# 普通解法
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
d = {}
for i in range(len(s) - 9):
k = s[i: i+10]
if k in d:
d[k] = True
else:
d[k] = False
return [*filter(lambda x: d[x], d)]
该的位运算解法暂时没看懂，先记录着，有点晕了，后面继续看
LeetCode-36.只出现一次的数字
这题比较简单，想到异或运算，相同为0，不同为1的规则就可以很快求解了
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 非空数组暂时不用判断
from functools import reduce
return reduce(lambda a, b: a ^ b, nums)
LeetCode-137.只出现一次的数字 II
## 普通解法
class Solution:
def singleNumber(self, nums):
return (3 * sum(set(nums)) - sum(nums)) // 2
推广到一般情况：
位运算的解法是有限状态机+位运算，感觉有点难理解，自己推敲一遍勉强可以理解，自己画一个状态表，然后推导出响应的公式就比较好了。
我是先看题解1， 在看题解2，才搞明白了。
几乎每道题都能看到题解2的作者，佩服不已，时而习之，但求甚解。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ones, twos = 0, 0
for num in nums:
ones = ones ^ num & ~twos
twos = twos ^ num & ~ones
return ones
LeetCode-260. 只出现一次的数字 III
注意：
- 结果输出的顺序并不重要，对于上面的例子，
[5, 3]也是正确答案。 - 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
根据前面找一个不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。
那么通过什么把数组分成两组呢？
放眼到二进制，我们要找的这两个数字是不同的，所以它俩至少有一位是不同的，所以我们可以根据这一位，把数组分成这一位都是 1 的一类和这一位都是 0 的一类，这样就把这两个数分到两组里了。
那么怎么知道那两个数字哪一位不同呢？
回到我们异或的结果，如果把数组中的所有数字异或，最后异或的结果，其实就是我们要找的两个数字的异或。而异或结果如果某一位是 1，也就意味着当前位两个数字一个是 1 ，一个是 0，也就找到了不同的一位。
以上思路源于作者：windliang
class Solution:
def FindNumsAppearOnce(self, nums):
length = len(nums)
if length <= 0:
return nums
result = 0
# 先将所有数子异或得到一个值
for num in nums:
result ^= num
# 找到这个值最低位二进制位1的位置，根据这个位置来区分两个数组，分别异或求出只出现一次的数字
firstBitIndex = self.FindFirstBit(result)
n1, n2 = 0, 0
for num in nums:
if self.IsSameBit(num, firstBitIndex):
n1 ^= num
else:
n2 ^= num
return n1, n2
def FindFirstBit(self, num):
indexBit = 0
while num & 1 == 0:
indexBit += 1
num = num >> 1
return indexBit
def IsSameBit(self, num, indexBit):
num = num >> indexBit
return num & 1
# 解放2
class Solution2:
def FindNumsAppearOnce(self, nums):
length = len(nums)
if length <= 0:
return []
diff = 0
for i in nums:
diff ^= i
n1, n2 = 0, 0
minDiff = self.getMinDiff(diff)
for num in nums:
if minDiff & num == 0:
n1 ^= num
n2 = diff ^ n1
return n1, n2
def getMinDiff(self, num):
# 保留一个低位是1的数字
# 取负号其实就是先取反，再加 1，需要 补码 的知识。最后再和原数相与就会保留最低位的 1。比如 1010，先取反是 0101，再加 1，就是 0110，再和 1010 相与，就是 0010 了
return num & (-num)
如何得到二进制位只有一个1的数，几种方法
取负号其实就是先取反，再加 1，需要 补码 的知识。最后再和原数相与就会保留最低位的 1。比如 1010，先取反是 0101，再加 1，就是 0110，再和 1010 相与，就是 0010 了。
n & (n - 1) 的操作在 191 题 用过，它可以将最低位的 1 置为 0。比如 1110，先将最低位的 1 置为 0 就变成 1100，然后再和原数 1110 异或，就得到了 0010
先减 1，再取反，再相与。比如 1010 减 1 就是 1001，然后取反 0110，然后和原数 1010 相与，就是 0010 了
mask=1
while((diff & mask)==0):
mask <<= 1
# mask 就是我们要构造的了
这里 的做法
参考资料
补码为什么按位取反再加一认真看完会有收获的。