位运算

位运算

1. 基础运算符

1.1 与运算（\&）

• 含义：对应位都为 $1$ 时结果位为 $1$，否则为 $0$
• 例：
$6=110_2,\ 5=101_2$
$6\ \&\ 5 = 100_2 = 4$



1.2 或运算（|）



• 含义：对应位只要有一个为 $1$，结果位为 $1$
• 例：
$6=110_2,\ 5=101_2$
$6\ |\ 5 = 111_2 = 7$



1.3 取反运算（~)



• 含义：$0\leftrightarrow 1$（对所有位取反）
• 例：
$5 = 00000101_2$
$\sim 5 = 11111010_2$
（在常见补码表示下，这个结果对应十进制 $-6$）



1.4 异或运算（^）



• 含义：对应位不同为 $1$，相同为 $0$
• 例：
$6=110_2,\ 5=101_2$
$6\ \hat{}\ 5 = 011_2 = 3$

---



2. 移位运算符





2.1 左移（<<）



• 含义：整体向左移动，低位补 $0$
• 直观效果：相当于乘以 $2^k$
• 例：
$3=00000011_2$
$3 \ll 2 = 00001100_2 = 12$



2.2 右移（>>）



• 含义：整体向右移动，低位被舍弃
• 直观效果：相当于除以 $2^k$ 并向下取整
• 例：
$13=00001101_2$
$13 \gg 2 = 00000011_2 = 3$



3. 位运算性质





3.1 异或性质（\^）



• 交换律、结合律成立
• 自反：$a \oplus a = 0$
• 与 $0$ 的关系：$a \oplus 0 = a$
• 可逆性：$(a \oplus b) \oplus b = a$



3.2 与性质（\&）



• 交换律、结合律成立
• 幂等：$a\ \&\ a = a$
• 吸收：$a\ \&\ 0 = 0$，$a\ \&\ \text{全1} = a$
• 递减：$a\ \&\ b \leq \min(a,b)$



3.3 或性质（|）



• 交换律、结合律成立
• 幂等：$a | a = a$
• 吸收：$a | 0 = a$，$a | \text{全1} = \text{全1}$
• 递增：$a | b \geq \max(a,b)$



4. 位运算技巧





4.1 判断某一位是否为 $1$



• 思路：构造掩码 $mask=1\ll k$，用与运算判断第 $k$ 位是否为 $1$
• 表达式：$x\ \&\ (1\ll k)$
• 例：
$x=13=1101_2$
- 判断第 $2$ 位：$mask=0100_2$
$1101_2\ \&\ 0100_2=0100_2\neq 0$，所以第 $2$ 位是 $1$
- 判断第 $1$ 位：$mask=0010_2$
$1101_2\ \&\ 0010_2=0000_2=0$，所以第 $1$ 位是 $0$



4.2 将某一位置 $1$ / 置 $0$ / 翻转



• 置 $1$：$x\ |=\ (1\ll k)$
• 置 $0$：$x\ \&=\ \sim(1\ll k)$
• 翻转：$x\ \hat{}=\ (1\ll k)$
• 例：$x=10=1010_2$

(1) 置第 $0$ 位为 $1$
$k=0$，$1\ll 0=0001_2$
$$ \begin{aligned} x' &= x\ |\ (1\ll 0) \\ &= 1010_2\ |\ 0001_2 \\ &= 1011_2 \\ &= 11 \end{aligned} $$

(2) 置第 $1$ 位为 $0$
$k=1$，$1\ll 1=0010_2$，$\sim(1\ll 1)=\sim 0010_2=1101_2$
$$ \begin{aligned} x' &= x\ \&\ \sim(1\ll 1) \\ &= 1010_2\ \&\ 1101_2 \\ &= 1000_2 \\ &= 8 \end{aligned} $$

(3) 翻转第 $3$ 位（$0\leftrightarrow 1$）
$k=3$，$1\ll 3=1000_2$
$$ \begin{aligned} x' &= x\ \hat{}\ (1\ll 3) \\ &= 1010_2\ \hat{}\ 1000_2 \\ &= 0010_2 \\ &= 2 \end{aligned} $$



4.3 找最低位的 $1$（$lowbit$）与删除最低位的 $1$



• $lowbit$：$lowbit(x)=x\ \&\ (-x)$（提取最低位的 $1$ 所代表的值）
• 删除最低位的 $1$：$x\ \&\ (x-1)$
• 例：
$x=12=1100_2$
- $lowbit(x)=0100_2\ (=4)$
- $x\ \&\ (x-1)=1100_2\ \&\ 1011_2=1000_2\ (=8)$



4.4 统计二进制中 $1$ 的个数



• 方法：不断删除最低位的 $1$，删除次数就是 $1$ 的个数
操作：反复执行 $x\ \&=\ (x-1)$
• 例：
$x=13=1101_2$
$1101\rightarrow 1100\rightarrow 1000\rightarrow 0000$
共 $3$ 次，所以 $popcount(13)=3$



4.5 判断是否为 $2$ 的幂



• 结论：对 $x0$，若 $x\ \&\ (x-1)=0$，则 $x$ 是 $2$ 的幂
（$2$ 的幂在二进制中只有一个 $1$）
• 例：
- $8=1000_2$：$8-1=7=0111_2$，$1000_2\ \&\ 0111_2=0000_2$，是 $2$ 的幂
- $12=1100_2$：$12-1=11=1011_2$，$1100_2\ \&\ 1011_2=1000_2\neq 0$，不是 $2$ 的幂



4.6 用整数的二进制位表示集合及子集枚举



• 集合表示（状态压缩）：用一个整数 $mask$ 表示集合
- 第 $i$ 位为 $1$：元素 $i$ 在集合中
- 第 $i$ 位为 $0$：元素 $i$ 不在集合中
• 例：
有 $4$ 个元素 $\{0,1,2,3\}$，$mask=13=1101_2$
表示集合为 $\{0,2,3\}$（第 $0,2,3$ 位为 $1$）



ex 子集枚举 / 超集枚举



设全集大小为 $n$，全集掩码 $U=(1\ll n)-1$。



1) 子集枚举（枚举 $mask$ 的所有子集 $sub$）





for (int sub = mask; ; sub = (sub - 1) & mask) {
    if (sub == 0) break;
}





2) 超集枚举（枚举所有 $sup \supseteq mask$）



做法：先枚举可选位 $free = U \oplus mask$ 的子集 $t$，再令 $sup = mask \mid t$。



int free = U ^ mask;
for (int t = free; ; t = (t - 1) & free) {
    int sup = mask | t;
    if (t == 0) break;
}





5. 常用函数





5.1 统计二进制中 $1$ 的个数（popcount）



• __builtin_popcount(x)
• __builtin_popcountll(x)



5.2 末尾连续 $0$ 的个数（ctz）



• __builtin_ctz(x)
• __builtin_ctzll(x)
• 注意：当 $x=0$ 时结果未定义（调用前需保证 $x\neq 0$）



5.3 前导连续 $0$ 的个数（clz）



• __builtin_clz(x)
• __builtin_clzll(x)
• 注意：当 $x=0$ 时结果未定义（调用前需保证 $x\neq 0$）



5.4 最高位 $1$ 的位置（$0$-based）



• 对 $x0$：
pos = 31 - __builtin_clz(x)（$32$ 位）
pos = 63 - __builtin_clzll(x)（$64$ 位）



5.5 最低位 $1$ 的位置（$0$-based）



• 对 $x0$：