本文最后更新于 599 天前,其中的信息可能已经有所发展或是发生改变。
位运算
位运算: 直接对整数在内存中的二进制位进行操作。比如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 = ~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