许多小伙伴见到位运算的题目就头大。其实，位运算是有基本的套路的。好比要你做四则综合运算，你只要把加减乘除学会，四则综合那都不是事儿。
位运算的加减乘除
这只是一个形象的说法，是指解决位运算的问题时，经常需要用的几个操作。
取出非负整数的各个位
位运算的问题基本功，将非负整数的给个位上是0还是1给取到。代码很简单，希望你背下来，不要觉得背很low，我知道不少进谷歌的，就是背题背进去的。
L= len(bin(num))
num_bits = [(num >> i) & 1 for i in range(L)][::-1]
一个数和1做逻辑与，就可以测出它最右边的bit是0还是1。比如5的二进制表示是101，它最右边的bit是1，与1作逻辑与后的值也是1。
代码中[::-1]是将bit按照从左到右的顺序排列。
将非负整数二进制表示中最右边的1置0
代码如下：
n = n&(n-1)
我们还是用5（101）来举例。5-1是4，4的二进制表示是100。101和100做逻辑与，是100，恰好将5最右边的1置0了。建议你自己找个非负整数试一下，就可以理解这种方法的正确性。
将非负整数二进制表示中除最右边的1之外的位全部置0
这个操作和上个操作刚好互补。上面的操作是仅置0最右边的1，这个操作是仅保留最右边的1。实现同样是一行代码，关于这个结论的正确性，需要用到补码的知识，这里就不细讲了，大家可以直接背住：
n = n&(-n)
异或运算的小结论
0和任意比特 x 异或结果还是 x 本身。
如果a，b两个值相同，异或结果为0
熟悉了以上的小结论，就可以拿下不少leetcode的题目了。
leetcode真题练手
比特位计数
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的1的数目并将它们作为数组返回。
示例 1:
输入: 2 输出: [0,1,1] 示例 2:
输入: 5 输出: [0,1,1,2,1,2]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/counting-bits 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
可以用 n&(n-1)这个操作，不断将一个数最右边的1置0，一直到n为0，据此统计出n中bit为1的个数。代码如下：
class Solution:
def countBits(self, num: int) -> List[int]:
res = [0] * (num+1)
for i in range(1, num+1):
cnt = 0
j = i
while i&(i-1) != i:
cnt += 1
i &= (i-1)
res[j] = cnt
return res
数字范围按位与
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7] 输出: 4 示例 2:
输入: [0,1] 输出: 0
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
通过观察可知，对所有数字执行按位与运算的结果是所有对应二进制字符串的公共前缀再用零补上后面的剩余位。如图所示：
你要是问我怎么观察到的，答案就是看别人答案后背下来的！！
所以，问题转化成了求m和n的公共前缀，那我们可以再次使用n&(n-1)操作，不断将n最右边的1清除，直到n<=m时，n中包含的就是公共前缀了。代码实现如下：
class Solution:
def rangeBitwiseAnd(self, m: int, n: int) -> int:
while m < n:
n = n & (n - 1)
return n
只出现一次的数字
给定一个非负整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5] 输出: [3,5]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/single-number-iii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
首先，我们把所有的数字都进行级联异或运算，假设最后的结果是bitmask，根据结论如果a，b两个值相同，异或结果为0。则最后的结果bitmask实际上就是两个只出现一次的元素的异或结果。
那我们现在的任务就是从这个异或的结果中将这两个数拆出来。具体办法就是就是再次遍历所有的数字进行异或，但是这次，我们要排除掉其中一个只出现一次的数字。办法就是我们需要一个特征，来区分两个只出现一次的数字。
此时，我们可以对bitmask使用 n&(-n)这个操作，仅保留最右边的1，这个就是两个只出现一次的数字中不相同的bit位。根据这个bit位就可以区分出这两个数。代码如下：
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
bitmask = 0
for num in nums:
bitmask ^= num
diff = bitmask & (-bitmask)
x = 0
for num in nums:
# bitmask which will contain only x
if num & diff:
x ^= num
return [x, bitmask^x]
通过num&diff，我们在第二轮异或运算中，就排除掉一个只出现一次的数字。细心的小伙伴可能会注意到，这样也会排除一部分出现了两次的数字，不过这个并不影响我们的最后结果。
总结
位运算的题目其实就是纸老虎，掌握好上面的几个基本操作，灵活运用，就不用再怕了。
