位运算

位运算： 直接对整数在内存中的二进制位进行操作。比如6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果。由于位运算直接在内存数据进行操作，不需要转为十进制，因此速度非常快。

异或的特点：

• x^0 = x
• x^1s = ~x。1s的意思是全为1的二进制数
• x^(~x) = 1s
  • x^x = 0
  • a^b = c $\rightarrow$ a^c = b, b^c = a。用来交换a、b的值。比如，设a = 1001, b = 1100，那么c = a^b = 0101，则a^c = 1100, b^c = 1001，正好可以交换a、b的值。
  • a^b^c = a^(b^c) = (a^b)^c

常用的位运算操作：

• 判断奇偶数：x & 1 ==1为奇数，x & 1 == 0为偶数
• 清零最低位的1：x & (x-1)
• 得到最低位的1：x & -x。-x为取反再加1

更为复杂的位运算操作：

• 将x最右边的n位清零：x & (~ 0<<n)
• 获取x的第n位值（0或1）：(x >> n) & 1
• 获取x的第n位幂值：x & (1 << (n-1))
• 仅将第n位置为1：x | (1<<n)
• 仅将第n位置为0：x & (~(1<<n))
• 将x最高位至第n位（含）清零：x & ((1 << n)-1)
• 将x第n位至第0位（含）清零：x & (~((1 << (n+1))-1))

例题

位1的个数：

此题为leetcode第191题。用“常用的位运算操作”里的“清零最低位的1”

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n != 0:
            res += 1
            n = n & (n - 1)
        return res

2的幂：

此题为leetcode第231题。2的幂化成2进制，它们都只有一个1，只要判断1的个数即可

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n != 0 and n & (n - 1) == 0

比特位计数

此题为leetcode第338题给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = [0] * (num + 1)
        for n in range(1, num + 1):
            res[n] += (res[n&(n-1)] + 1)
        return res

N皇后II，位运算解法

此题为leetcode第52题，常规用深度优先搜索解法，会用到集合去保存横竖、斜角方向上的状态，解法点这里。而使用位运算可以直接获得棋盘上可以放皇后的位置，可以提高效率。

class Solution:
    # 使用位运算解决
    def totalNQueens(self, n):
        if n < 1:
            return []
        self.count = 0
        self.DFS(n, 0, 0, 0, 0) 
        return self.count

    def DFS(self, n, row, col, pie, na):
        if row >= n:
            self.count += 1
            return 

        # 获得可以放皇后的位置
        bits = (~(col | pie | na)) & ((1 << n) - 1)

        # 递归
        while bits:
            p = bits & -bits    # 获得最低位的1，也就是遍历合法的位置
            self.DFS(n, row + 1, (col | p), (pie | p) << 1, (na | p) >> 1)
            bits = bits & (bits - 1)    # 去掉最低位的1