位运算

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$ 的幂

• 结论：对 $x>0$，若 $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）

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

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

• 对 $x>0$：
  pos = __builtin_ctz(x)（$32$ 位）
  pos = __builtin_ctzll(x)（$64$ 位）

【前置知识点】
1、进制转换

【思维导图】

【题目知识点分类】