📖 第 2.6 章：位运算

⏱ 预计阅读时间：55 分钟 | 难度：🟢 入门（USACO Bronze/Silver 必备）

前置条件

• 整数的二进制表示（知道什么是二进制即可）
• 基本 C++ 语法

🎯 学习目标

学完本章后，你将能够：

1. 看懂一个整数的二进制表示，并知道每一位像一个「开关」
2. 使用六种位运算符进行高效整数操作
3. 用位运算检查、设置、清除、翻转二进制位
4. 用整数作为「集合」（状压表示）进行集合运算
5. 枚举一个整数所有子集（状压 DP 基础）
6. 理解常见的位运算技巧（lowbit、快速判断 2 的幂等）

2.6.1 为什么要学位运算？

计算机存整数时，底层不是十进制的 0, 1, 2, 3...，而是一串二进制位。例如：

十进制 13 = 二进制 1101

可以把 1101 想成 4 个小灯泡：

位置：   3 2 1 0
二进制： 1 1 0 1
含义：   开 开 关 开

每一位都有自己的价值：

所以 13 = 8 + 4 + 1。

位运算就是直接操作这些小灯泡。普通加减乘除是对整个数字做运算；位运算是对数字内部的每一盏灯单独操作。

竞赛中的典型应用：

一个最小例子：为什么 x & 1 能判断奇偶？

一个数是否为奇数，只看二进制的最后一位：

12 = 1100，最后一位是 0，所以是偶数
13 = 1101，最后一位是 1，所以是奇数

1 的二进制只有最后一位是 1：

13 & 1
1101
0001
----
0001  -> 结果不是 0，所以 13 是奇数

12 & 1
1100
0001
----
0000  -> 结果是 0，所以 12 是偶数

这就是位运算的思维方式：不看整个数，只盯住你关心的那一位。

2.6.2 六种基本位运算符

直觉记忆

AND  &：两个都是1才得1（取交集：都有才保留）
OR   |：有一个是1就得1（取并集：有一个就保留）
XOR  ^：不同为1，相同为0（取差集/翻转：不一样才保留）
NOT  ~：0变1，1变0（取补集）

一位一位地算，别整串一起看

初学位运算时，最容易犯的错误是把 1100 & 1010 当成普通数字计算。实际上它是「同一列对同一列」计算：

  1100
& 1010
------
  1000

从右到左逐列看：

同理，| 是「只要有一个 1 就亮」，^ 是「两边不一样才亮」。

左移和右移：把灯泡整体搬家

<< 和 >> 不改变每一位本身，而是把整排二进制位往左或往右移动。

1       = 0001
1 << 1  = 0010 = 2
1 << 2  = 0100 = 4
1 << 3  = 1000 = 8

所以 1 << k 表示：只让第 k 位亮起来。

这也是后面所有模板的基础：

1 << k

可以理解成一个「只选中第 k 位的小工具」。

2.6.3 常用位操作模板

先记住一个核心工具：

1 << k

它表示一个只有第 k 位是 1 的数字。注意第 k 位从右往左数，并且从 0 开始：

k:       3 2 1 0
1 << 0 = 0 0 0 1
1 << 1 = 0 0 1 0
1 << 2 = 0 1 0 0
1 << 3 = 1 0 0 0

假设 x = 13 = 1101，我们想操作第 2 位，可以先造出面具 1 << 2 = 0100。后面所有操作，都是让 x 和这个面具做运算。

1. 检查第 k 位是否为 1

问题： 给你一个整数 x，怎样知道它的第 k 位是不是亮着？

bool check(int x, int k) {
    return (x >> k) & 1;
}

这段代码分成两步：

1. x >> k：把第 k 位移动到最右边。
2. & 1：只检查最右边这一位是不是 1。

为什么要移动到最右边？因为最右边最容易检查。只要和 1 做 &，就能保留最后一位，其他位都会变成 0。

假设：

x = 13 = 1101
k = 2

第 2 位是从右往左数的第三位：

位置：   3 2 1 0
x：      1 1 0 1
             ↑
          第 2 位

计算过程：

x >> 2：
1101 >> 2 = 0011

再 & 1：
0011
0001
----
0001

结果是 1，说明 13 的第 2 位是亮着的。

如果检查第 1 位：

x >> 1：
1101 >> 1 = 0110

再 & 1：
0110
0001
----
0000

结果是 0，说明第 1 位没有亮。

2. 将第 k 位设为 1（置位）

问题： 怎样把某一盏灯打开？如果它本来就是开的，就保持打开。

int set_bit(int x, int k) {
    return x | (1 << k);
}

这里的关键是 |：只要两边有一个是 1，结果就是 1。

所以我们先用 1 << k 做一个只在第 k 位为 1 的面具，再用 | 把这一位打开。

假设：

x = 13 = 1101
k = 1
mask = 1 << 1 = 0010

计算：

  1101
| 0010
------
  1111 = 15

第 1 位原来是 0，现在被打开了。

如果这一位本来就是 1，也不会有问题：

x = 13 = 1101
k = 2
mask = 0100

  1101
| 0100
------
  1101

第 2 位本来就是 1，置位后仍然是 1。

3. 将第 k 位设为 0（清位）

问题： 怎样把某一盏灯关掉？如果它本来就是关的，就保持关闭。

int clear_bit(int x, int k) {
    return x & ~(1 << k);
}

这段代码看起来比置位难一点，因为多了一个 ~。我们一步一步拆开：

1. 1 << k：制造一个只有第 k 位是 1 的面具。
2. ~(1 << k)：把面具反过来，让第 k 位变成 0，其他位变成 1。
3. x & ~(1 << k)：用 & 保留其他位，同时把第 k 位变成 0。

假设：

x = 13 = 1101
k = 2

先得到面具：

1 << 2 = 0100

反过来：

~0100 = ...1011

为了方便观察，我们只看最低 4 位，就是：

1011

然后做 &：

  1101
& 1011
------
  1001 = 9

第 2 位被关掉了，其他位保持原样。

如果第 k 位本来就是 0，清位也不会改变它：

x = 13 = 1101
k = 1
mask 反过来后最低 4 位是 1101

  1101
& 1101
------
  1101

4. 翻转第 k 位

问题： 怎样让某一盏灯“反过来”？开着就关掉，关着就打开。

int flip_bit(int x, int k) {
    return x ^ (1 << k);
}

这里用的是 ^。它的规则是：相同得 0，不同得 1。

更适合记成：

某一位 ^ 0：保持不变
某一位 ^ 1：发生翻转

所以 x ^ (1 << k) 的意思是：只让第 k 位和 1 做异或，其他位和 0 做异或，因此只有第 k 位会翻转。

例 1：把第 1 位从 0 翻成 1。

x = 13 = 1101
k = 1
mask = 0010

  1101
^ 0010
------
  1111 = 15

例 2：把第 2 位从 1 翻成 0。

x = 13 = 1101
k = 2
mask = 0100

  1101
^ 0100
------
  1001 = 9

所以翻转不是固定变成 1，也不是固定变成 0，而是：原来是什么，就变成相反的状态。

5. 判断一个数是否是 2 的幂

问题： 怎样快速判断 x 是不是 1, 2, 4, 8, 16... 这样的数？

bool is_power_of_two(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

先观察 2 的幂在二进制中的样子：

它们都有一个共同特点：二进制里只有一个 1。

再看 x - 1 会发生什么。以 x = 8 为例：

x     = 1000
x - 1 = 0111

做 &：

  1000
& 0111
------
  0000

结果是 0，说明 8 只有一个 1，所以它是 2 的幂。

再看一个不是 2 的幂的数，比如 12：

x     = 1100
x - 1 = 1011

  1100
& 1011
------
  1000

结果不是 0，说明 12 不只一个 1，所以不是 2 的幂。

为什么还要写 x > 0？因为 0 不是 2 的幂。如果不加这个条件，0 & -1 也会得到 0，容易误判。

6. 获取最低有效位：lowbit

问题： 怎样找到一个数从右往左数，第一盏亮着的灯？

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

lowbit(x) 返回的不是第几个位置，而是这一位对应的数值。

例如：

x = 12 = 1100

从右往左看：

位置：   3 2 1 0
x：      1 1 0 0
           ↑
      最右边的 1 在第 2 位

第 2 位的价值是 4，所以：

lowbit(12) = 4

用补码计算就是：

12 的二进制：  0000 1100
-12（补码）：  1111 0100
12 & (-12)：   0000 0100 = 4

这在树状数组中很常见。你可以暂时先记住：lowbit(x) 能拿到 x 最右边那个 1 代表的值。

7. 清除最低有效位

问题： 怎样把最右边那个 1 删除掉？

int clear_lowest(int x) {
    return x & (x - 1);
}

它和判断 2 的幂用的是同一个核心技巧。

假设：

x = 12 = 1100
x - 1 = 11 = 1011

计算：

  1100
& 1011
------
  1000 = 8

可以看到，x 最右边的那个 1 被清掉了。

再来一个例子：

x = 10 = 1010
x - 1 = 9 = 1001

  1010
& 1001
------
  1000 = 8

这件事有什么用？如果我们不断清除最低位的 1，就能统计一个数里面有多少个 1。

8. 统计二进制中 1 的个数：popcount

问题： 怎样知道一个整数的二进制里有几盏灯亮着？

C++ 提供了内置函数：

int count_ones(int x) {
    return __builtin_popcount(x);
}

例如：

x = 13 = 1101

里面有三位是 1，所以：

count_ones(13) = 3

如果不用内置函数，也可以用刚才的 clear_lowest 思想手写：

int count_ones_manual(int x) {
    int cnt = 0;
    while (x) {
        x &= x - 1;
        cnt++;
    }
    return cnt;
}

以 x = 13 = 1101 为例：

第 1 次：1101 -> 1100，cnt = 1
第 2 次：1100 -> 1000，cnt = 2
第 3 次：1000 -> 0000，cnt = 3

循环结束时，说明所有 1 都被清掉了，所以原来一共有 3 个 1。

常用模板汇总

前面我们已经把每个函数都单独拆开讲过了。真正写题时，可以把下面这组函数当成工具箱：

// ===== 单个位的操作（第 k 位，从 0 开始计数）=====

// 检查第 k 位是否为 1
bool check(int x, int k) { return (x >> k) & 1; }

// 将第 k 位设为 1（置位）
int set_bit(int x, int k) { return x | (1 << k); }

// 将第 k 位设为 0（清位）
int clear_bit(int x, int k) { return x & ~(1 << k); }

// 翻转第 k 位（0→1，1→0）
int flip_bit(int x, int k) { return x ^ (1 << k); }


// ===== 常用技巧 =====

// 判断 x 是否为 2 的幂（且 x > 0）
bool is_power_of_two(int x) { return x > 0 && (x & (x - 1)) == 0; }

// 获取最低有效位（lowbit，树状数组核心）
int lowbit(int x) { return x & (-x); }

// 清除最低有效位
int clear_lowest(int x) { return x & (x - 1); }

// 统计 x 中 1 的个数（popcount）
int count_ones(int x) { return __builtin_popcount(x); }     // 内置函数
// 或手动：
int count_ones_manual(int x) {
    int cnt = 0;
    while (x) { x &= x - 1; cnt++; }  // 每次清除最低位的1
    return cnt;
}

本节总结

2.6.4 用整数表示集合（状压）

当元素数量 N ≤ 30 时，可以用一个 int 整数的 N 个二进制位表示一个集合。

编码规则： 第 i 个元素在集合中 ↔ 第 i 位为 1。

把集合想象成签到表

如果有 5 个学生，编号为 0, 1, 2, 3, 4，我们可以用 5 个开关表示他们有没有被选中：

学生编号： 4 3 2 1 0
是否选中： 1 0 1 0 1

这表示选中了学生 {0, 2, 4}。写成二进制就是 10101，十进制是 21。

这样做的好处是：一个整数就能保存一个集合，而且加入、删除、检查元素都能用 O(1) 完成。

// 集合 {0, 2, 4} 表示为：
// 二进制：10101 = 21

int S = 0;           // 空集
S = set_bit(S, 0);   // 加入元素 0：S = 00001 = 1
S = set_bit(S, 2);   // 加入元素 2：S = 00101 = 5
S = set_bit(S, 4);   // 加入元素 4：S = 10101 = 21

// 检查元素 2 是否在集合中
bool has2 = check(S, 2);  // true

// 删除元素 2
S = clear_bit(S, 2);      // S = 10001 = 17

// 集合大小
int size = __builtin_popcount(S);  // 2

集合运算

int A = 0b1100;  // {2, 3}
int B = 0b1010;  // {1, 3}

int inter = A & B;    // 交集：0b1000 = {3}
int unio  = A | B;    // 并集：0b1110 = {1, 2, 3}
int diff  = A & ~B;   // 差集 A-B：0b0100 = {2}
int xor_s = A ^ B;    // 对称差：0b0110 = {1, 2}

这些集合运算其实和数学里的集合完全对应：

例如 A = {2, 3}，B = {1, 3}：

A 和 B 都有 3，所以交集是 {3}
A 或 B 出现过 1、2、3，所以并集是 {1,2,3}
A 有但 B 没有的是 2，所以 A-B 是 {2}
只出现一次的是 1 和 2，所以对称差是 {1,2}

2.6.5 枚举所有子集

N 个元素的集合有 2^N 个子集，可以用 for (int s = 0; s < (1 << n); s++) 枚举。

为什么是 2^N？因为每个元素只有两种选择：

不选这个元素 -> 0
选择这个元素 -> 1

如果有 3 个元素，每个元素都有选/不选两种状态，总数就是：

2 × 2 × 2 = 8

也就是 2^3 个子集。

先看 n = 3 的完整例子

所以枚举整数 0 到 2^n - 1，其实就是枚举了所有开关组合，也就是所有子集。

// 枚举 n 个元素的所有子集
void enumerate_subsets(int n) {
    for (int s = 0; s < (1 << n); s++) {
        cout << "子集 " << s << "（二进制 " << bitset<4>(s) << "）：{";
        for (int i = 0; i < n; i++) {
            if (check(s, i)) cout << i << " ";
        }
        cout << "}\n";
    }
}
// enumerate_subsets(3) 输出 2^3 = 8 个子集

枚举某集合 S 的所有子集

有时我们不是枚举全集 {0,1,2,...,n-1} 的所有子集，而是枚举一个已经给定的集合 S 的所有子集。

例如：

S = 10110 = {1,2,4}

我们只想枚举由 {1,2,4} 组成的子集，不能出现元素 0 或 3。

// 枚举 S 的所有非空子集（时间：O(3^n)，见下面说明）
for (int sub = S; sub > 0; sub = (sub - 1) & S) {
    // 处理子集 sub
    // ...
}
// 原理：sub = (sub - 1) & S 每次在 S 的范围内减 1，跳过不属于 S 的位

为什么 sub = (sub - 1) & S 不会跑出 S？

sub - 1 会让二进制发生变化，可能产生一些不属于 S 的 1。再 & S 一次，就像用 S 做过滤器：只有 S 里本来是 1 的位置才能保留下来。

以 S = 10110 为例，枚举过程大致是：

10110
10100
10010
10000
00110
00100
00010

每一步都只使用了 S 中允许的位。

2.6.6 实战例题：状压 + 位运算

前面我们学的是「工具」，这一节开始把工具放进题目里。做位运算题时，可以按照这个顺序思考：

1. 每一位代表什么？ 是一个元素、一个城市，还是一个开关？
2. 1 表示什么，0 表示什么？ 例如 1 表示已选择，0 表示未选择。
3. 要做的操作对应哪个位运算？ 加入用 |，删除用 & ~，检查用 & 或右移。
4. 状态数量有多少？ 如果有 n 个开关，通常会有 2^n 种状态。

例题：集合和问题

给定 N 个数字（N ≤ 20），找有多少个子集的和恰好等于目标值 target。

为什么可以暴力枚举？

N ≤ 20 时，一共有 2^20 = 1,048,576 个子集，大约一百万个。每个子集再扫一遍最多 20 个数，大约两千万次操作，C++ 通常可以接受。

状态设计：

• s 是一个二进制集合。
• s 的第 i 位为 1，表示选择了 a[i]。
• 枚举所有 s，就等于枚举所有可能的选择方案。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int ans = 0;
    for (int s = 0; s < (1 << n); s++) {
        int sum = 0;
        for (int i = 0; i < n; i++)
            if (check(s, i)) sum += a[i];
        if (sum == target) ans++;
    }
    
    cout << ans << "\n";
}
// 复杂度：O(2^N × N)，N=20 时约 2×10^7，可以通过

例题：旅行商问题（状压 DP 基础）

N 个城市（N ≤ 20），从城市 0 出发经过所有城市恰好一次回到 0，求最短路。

这个题比集合和更难，因为它不仅要记录「访问过哪些城市」，还要记录「现在停在哪个城市」。

状态设计：

dp[mask][v]

含义是：

• mask 表示已经访问过的城市集合。
• v 表示当前所在城市。
• dp[mask][v] 表示在这种情况下的最短距离。

例如 mask = 01011 表示已经访问过城市 {0,1,3}；如果 v = 3，就表示当前停在城市 3。

转移思路：

如果当前在城市 u，下一步可以去一个还没访问过的城市 v。这时：

new_mask = mask | (1 << v);

意思是把城市 v 标记为「已经访问」。

#include <bits/stdc++.h>
using namespace std;

int n;
int dist[20][20];
int dp[1 << 20][20];  // dp[mask][v] = 访问了 mask 中的城市，当前在 v，的最短距离

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dist[i][j];
    
    // 初始化
    for (auto& row : dp) fill(row, row + n, INT_MAX / 2);
    dp[1][0] = 0;  // 从城市 0 出发，mask=1（只访问了0）
    
    // 枚举所有状态
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == INT_MAX / 2) continue;
            if (!check(mask, u)) continue;
            
            // 尝试移动到下一个未访问的城市 v
            for (int v = 0; v < n; v++) {
                if (check(mask, v)) continue;  // 已访问
                int new_mask = set_bit(mask, v);
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    // 所有城市都访问后（mask = (1<<n)-1），回到城市 0
    int ans = INT_MAX;
    int full = (1 << n) - 1;
    for (int u = 1; u < n; u++)
        ans = min(ans, dp[full][u] + dist[u][0]);
    
    cout << ans << "\n";
    // 复杂度：O(2^N × N^2)，N=20 时约 4×10^8（偏大，N=15~18 通常可行）
}

⚠️ 常见错误

💪 练习题

🟢 题目 1：奇偶统计

给定整数 x，输出它的二进制表示中 1 的个数（popcount），以及是否是 2 的幂。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x; cin >> x;
    cout << __builtin_popcount(x) << "\n";
    cout << (x > 0 && (x & (x-1)) == 0 ? "是2的幂" : "不是2的幂") << "\n";
}

🟢 题目 2：位翻转

给定整数 x 和位置数组 k[]，将 x 的这些位翻转后输出结果。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x, m; cin >> x >> m;
    while (m--) {
        int k; cin >> k;
        x ^= (1 << k);  // XOR 翻转第 k 位
    }
    cout << x << "\n";
}

🟡 题目 3：子集枚举

给定 N 个数字（N ≤ 20），找所有和为偶数的子集数量。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int cnt = 0;
    for (int s = 0; s < (1 << n); s++) {
        int sum = 0;
        for (int i = 0; i < n; i++)
            if ((s >> i) & 1) sum += a[i];
        if (sum % 2 == 0) cnt++;
    }
    cout << cnt << "\n";
    // 答案总是 2^(n-1)（如果有奇数）
}

🔴 题目 4：最大异或子集

给定 N 个数字（N ≤ 20），选出一个非空子集，使子集内所有数字的异或和最大，输出该最大值。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int ans = 0;
    for (int s = 1; s < (1 << n); s++) {
        int xor_sum = 0;
        for (int i = 0; i < n; i++)
            if ((s >> i) & 1) xor_sum ^= a[i];
        ans = max(ans, xor_sum);
    }
    cout << ans << "\n";
}

🔴 题目 5：USACO Bronze 风格 — 奶牛体操（位运算版）

N 头奶牛（N ≤ 20），K 轮训练。每轮训练中，奶牛按排名从 1 到 N 排列。定义一对奶牛 (i, j) 是「一致的」，若在所有 K 轮中 i 都排在 j 前面。用位运算统计有多少对奶牛是一致的。

输入： 第一行 K N，接下来 K 行每行 N 个整数（1~N 的排列，表示该轮的排名顺序）。

样例输入：

3 4
4 1 2 3
4 1 3 2
4 2 1 3

样例输出： 4

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int K, N;
    cin >> K >> N;

    // before[i] 的第 j 位 = 奶牛 j 在所有已完成轮次中是否始终排在 i 前面
    vector<int> before(N, (1 << N) - 1);  // 初始全1，逐轮 AND

    for (int round = 0; round < K; round++) {
        // 读取排名：rank[0]=第1名的奶牛编号...
        vector<int> ranking(N);
        for (int p = 0; p < N; p++) cin >> ranking[p];

        // mask 记录当前已出现的奶牛（排在前面）
        int mask = 0;
        for (int p = 0; p < N; p++) {
            int cow = ranking[p] - 1;  // 转 0-indexed
            before[cow] &= mask;       // AND 上当前排在前面的奶牛集合
            mask |= (1 << cow);        // 将当前奶牛加入已出现集合
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++)
        ans += __builtin_popcount(before[i]);
    cout << ans << "\n";
}

💡 章节联系： 位运算是状压 DP（第 6.3 章进阶 DP）的基础工具，也用于树状数组的 lowbit 操作（第 5.7 章）。掌握本章后，你将能读懂绝大多数竞赛代码中的位运算技巧。

本章小结

• 位就是开关：每一位只有 0 和 1 两种状态。
• 1 << k 是核心工具：它能制造一个只选中第 k 位的掩码。
• 单个位操作有固定套路：检查、置位、清位、翻转分别对应不同位运算。
• 状压就是用整数存集合：第 i 位为 1 表示第 i 个元素被选中。
• 枚举子集就是枚举开关组合：0 到 (1 << n) - 1 覆盖了所有选/不选方案。
• 不要只背代码：做题时先问"每一位代表什么"，再选择合适的位运算。