第 8 章：位运算与编码 (Bit Manipulation)

8.1 基础操作符：记住这六个符号

假设我们有两个 8 位二进制数： $A = 0011\_1100$ ($60$) $B = 0000\_1101$ ($13$)

💡 必会的移位技巧

在算法竞赛中，我们很少写 pow(2, n)，因为浮点数运算慢且有精度误差。我们用移位代替：

• $2^N$ $\rightarrow$ 1 << n
• $x \times 2$ $\rightarrow$ x << 1
• $x \div 2$ $\rightarrow$ x >> 1 (常用于二分 mid = (l+r) >> 1)

8.2 常用位运算骚操作

这些技巧能显著缩短你的代码长度：

1. 判断奇偶数： if (x & 1) $\rightarrow$ x 是奇数 if (!(x & 1)) $\rightarrow$ x 是偶数 原理：奇数的二进制最后一位肯定是 1。

2. 交换两个数 (不使用临时变量)： 虽然不推荐在工程中写，但理解异或性质很有趣：$A \oplus A = 0$。

   a ^= b;
   b ^= a;
   a ^= b;

3. 异或的妙用：找单身狗 题目：数组里有一个数只出现了一次，其他数都出现了两次。找出那个数。 解法：把数组里所有数异或起来，结果就是那个数。 原理：a ^ b ^ a 等价于 a ^ a ^ b = 0 ^ b = b。

8.3 二进制状态压缩 (Bitmask)

这是位运算最强大的应用场景。 假设你有 $N$ 盏灯 ($N \le 20$)，每盏灯可以开或关。你想记录当前的开关状态。 不需要开一个 bool lights[20] 数组，只需要一个 int 整数 state。

集合与二进制的对应关系

如果 state = 21 (二进制 10101)：

• 第 0 位是 1 $\rightarrow$ 第 0 盏灯开了。
• 第 1 位是 0 $\rightarrow$ 第 1 盏灯关了。
• 第 2 位是 1 $\rightarrow$ 第 2 盏灯开了。
• ...

核心操作模板 (背诵)

假设 state 表示当前集合，i 是我们要操作的第 $i$ 个元素（下标从 0 开始）：

1. 查询（看第 $i$ 位是不是 1）： if (state & (1 << i))
2. 添加（把第 $i$ 位变成 1）： state = state | (1 << i);
3. 删除（把第 $i$ 位变成 0）： state = state & ~(1 << i); 解释：~(1 << i) 会生成一个只有第 $i$ 位是 0，其他位全是 1 的掩码。
4. 取反（把第 $i$ 位 0 变 1，1 变 0）： state = state ^ (1 << i);

8.4 Lowbit 操作：树状数组的基石

这是一个非常神奇的操作，在高级数据结构 树状数组 (Binary Indexed Tree / Fenwick Tree) 中是核心。

定义：lowbit(x) 返回 $x$ 的二进制表示中，最低位的 1 及其后面的 0 组成的数值。

• $x = 12$ (1100) $\rightarrow$ lowbit(12) = 4 (100)
• $x = 6$ (0110) $\rightarrow$ lowbit(6) = 2 (10)
• $x = 7$ (0111) $\rightarrow$ lowbit(7) = 1 (1)

公式：

int lowbit(int x) {
    return x & (-x);
}

原理：在计算机补码表示法中，-x 等于 ~x + 1。这会导致最低位的 1 及其右边保持不变，左边全部取反。两者做“与”运算，就只剩下了最低位的 1。

应用：计算一个数二进制里有几个 1？ 每次减去 lowbit(x)，直到 x 变成 0，减了几次就有几个 1。

int countSetBits(int x) {
    int cnt = 0;
    while (x > 0) {
        x -= (x & -x); // 每次消掉最后一个 1
        cnt++;
    }
    return cnt;
}
// 注：C++20 可以直接用 std::popcount(x)

8.5 实战：内置函数 (GCC Built-in Functions)

如果你用 GCC/G++ 编译器（洛谷、Codeforces 都是），可以直接使用这些超快的内置函数，不需要手写循环：

1. __builtin_popcount(x): 返回 x 二进制中 1 的个数。
2. __builtin_ctz(x): Count Trailing Zeros，返回末尾有几个 0。
3. __builtin_clz(x): Count Leading Zeros，返回前面有多少个 0 (基于 32 位整型)。

⚠️ 注意：如果是 long long 类型，要在函数名后面加 ll，例如 __builtin_popcountll(x)。

🧠 本章小结与练习

位运算看似玄学，实则是处理“集合”和“状态”的神器。

练习作业：

1. P1469 找筷子 (洛谷)：数组中成对出现的数字，只有一个落单，找出它。要求 $O(N)$ 且空间极小。（提示：异或）。
2. LeetCode 78. Subsets：给你一个数组，输出所有可能的子集。（提示：用 $0 \sim 2^N-1$ 的循环配合位运算来做）。
3. P1226 快速幂：回顾上一章的快速幂代码，看看里面的 b & 1 和 b >>= 1 是不是就是这一章的内容？

搞定了位运算，我们就拥有了处理前缀和与差分的基础逻辑（虽然它们看似只是加减法，但思想是通用的）。 接下来的这一章，将是你接触的第一个“预处理”算法——如何用 $O(1)$ 的时间求出任意区间的和？