本笔记内容来源于算法基础课

位运算

常用操作

$x$的二进制表示中的第$k$位

1. 先把第$k$位移动到最后一位 x >> k
2. 取出第一位 x & 1

模板

x >> k & 1

$x$的二进制表示中的最后一位1

lowbit(x) 返回二进制下最后一位1

x    _ _ _ _ 1 0 0 0 0
~x   ^ ^ ^ ^ 0 1 1 1 1
~x+1 ^ ^ ^ ^ 1 0 0 0 0

x & (~x+1) =  0 0 0 0 1 0 0 0 0
x & -x = lowbit(x)

模板

x & -x

一个数是否为2的幂

x > 0 && (x & (x - 1) == 0)

x > 0 && x == x & (-x)

例题

Acwing 801 经典模板应用
Acwing 85 位运算的性质