📖 第 2.6 章：位运算

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

前置条件

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

🎯 学习目标

学完本章后，你将能够：

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

2.6.1 为什么要学位运算？

位运算让你在 O(1) 时间内对整数的二进制位做操作。竞赛中的典型应用：

2.6.2 六种基本位运算符

直觉记忆

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

2.6.3 常用位操作模板

// ===== 单个位的操作（第 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;
}

逐步追踪 lowbit(12)：

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

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

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

编码规则： 第 i 个元素在集合中 ↔ 第 i 位为 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}

2.6.5 枚举所有子集

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

// 枚举 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 的所有子集

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

为什么是 O(3^n)？ 每个位有三种情况：在 S 中但不在 sub 中（1）、在 S 中且在 sub 中（2）、不在 S 中（自动跳过，只 1 种）。总计 2^(|S|) × 1^(n-|S|) 求和 = 3^n。

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

例题：集合和问题

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

#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，求最短路。

#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";
}

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