本文最后更新于:2 个月前

一、位运算

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

常用的逻辑运算符:
| 符号 | 描述 | 运算规则 |
| —— | —— | —————————————————————————————— |
| & | 与 | 两个都为1时,结果才为1 |
| | | 或 | 两个都为 0时,结果才为1 |
| ^ | 异或 | 相同为0,不同为1 |
| ~ | 取反 | 0变1,1变0 |
| << | 左移 | 各二进制位全部左移若干位,高位丢弃,低位补0 |
| >> | 右移 | 各二进制位全部右移若干位,对于无符号数,高位补0,;对于有符号数,有的补符号位(算数右移),有的补0(逻辑右移) |

异或的特点:

  • x^0 = x
  • x^1s = ~x1s的意思是全为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)位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)2的幂:

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

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

(3)比特位计数

此题为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

(4)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