位运算进阶

概念讲解

用二进制的眼光看变量

学习位运算，第一步不是背公式，而是习惯把变量看成一排固定的 0 和 1。对计算机来说，int x = 42; 在内存中并不是"42"这个十进制数，而是 32 个二进制位：

123int x = 42;
// 42 = 32 + 8 + 2 = 2^5 + 2^3 + 2^1
// 只看低 8 位，就是 00101010

记住两条规则：

位从 0 开始编号，最右边是第 0 位。 第 i 位上的 1 代表权值 $2^i$ 。例如 00101010 的第 1、3、5 位是 1，所以它的值是 $2^1+2^3+2^5=2+8+32=42$ 。
书写时高位在左、低位在右，和十进制数字的高低位方向一致。

十进制转二进制可以用"除 2 取余"，但竞赛中更实用的做法是熟记 2 的幂（1、2、4、8、16、32、64、128、256、512、1024……），把一个数拆成若干个 2 的幂之和，对应位置写 1、其余写 0。

手算难免出错，最好的办法是让程序直接把二进制打印出来，这就要用到 bitset。

bitset：把变量"打印"成二进制

std::bitset 是 C++ 标准库提供的定长位数组，包含在 <bitset> 头文件中（<bits/stdc++.h> 已经包含它）。调试时用一个整数构造 bitset，就能直接输出它的二进制表示：

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

int main() {
    int x = 42;
    cout << bitset<8>(x) << endl;   // 00101010
    cout << bitset<32>(x) << endl;  // 00000000000000000000000000101010
}

尖括号里的数字表示要看多少位，必须是编译期就能确定的常量。bitset<32>(x) 会把一个 int 的全部 32 位完整显示出来。做位运算题时，把两个操作数和结果都打印出来逐位对齐，运算过程一目了然：

1234cout << bitset<8>(6) << endl;       // 00000110
cout << bitset<8>(10) << endl;      // 00001010
cout << bitset<8>(6 & 10) << endl;  // 00000010  逐位对齐看"与"
cout << bitset<32>(-1) << endl;     // 11111111111111111111111111111111

最后一行揭示了一个重要事实：负数在计算机中以补码存储，-1 的 32 位全部是 1。这也解释了为什么位运算题目中常说"假设 int 为 32 位"。建议初学阶段每做一道位运算题，都先用 bitset 把中间结果打印出来观察。

即使不使用 bitset，也可以手写一个逐位打印的小工具，原理就是逐位取出 (x >> i) & 1：

12345void showBits(int x, int n = 8) {
    for (int i = n - 1; i >= 0; i--)
        cout << ((x >> i) & 1);  // 取出第 i 位，从高位到低位打印
    cout << "  (" << x << ")" << endl;
}

bitset 作为容器：常用操作

bitset 不只能"看"，还可以直接当作能按下标访问的位数组来运算，第 0 位同样在最右边：

1234567891011121314151617181920bitset<8> b;           // 00000000，默认全 0
bitset<8> a(42);       // 00101010，从整数构造（只取低 8 位）
bitset<8> c("1011");   // 00001011，从二进制字符串构造

b[0] = 1;              // 00000001，下标可读写第 i 位
b.set(2);              // 00000101，把第 2 位置 1
b.set();               // 11111111，不带参数表示全部置 1
b.reset(0);            // 11111110，把第 0 位清 0
b.reset();             // 00000000，全部清 0
b.flip(1);             // 00000010，翻转第 1 位
b.flip();              // 11111101，全部翻转

a.count();             // 1 的个数，相当于 __builtin_popcount
a.size();              // 总位数，这里是 8
a.test(3);             // 第 3 位是否为 1，比 a[3] 语义更明确
a.any();               // 是否至少有一个 1
a.none();              // 是否全为 0
a.all();               // 是否全为 1

unsigned long v = a.to_ulong();  // 再转回整数，v = 42

两个 bitset 之间可以直接做与、或、异或、移位，写法和整数完全相同：

12345bitset<8> x(6), y(10);
cout << (x & y) << endl;  // 00000010
cout << (x | y) << endl;  // 00001110
cout << (x ^ y) << endl;  // 00001100
cout << (x << 2) << endl; // 00011000

bitset 最大的实用价值是突破 64 位限制：用整数做状态压缩，long long 最多表示 64 个元素，而 bitset<1000> 可以轻松表示 1000 个二进制状态，整体做一次与/或运算只需要约 16 个机器字的时间。状压 DP、集合判重、布尔可达集合等场景常用它把复杂度降低约 64 倍。

枚举子集

1234// 枚举集合 s 的所有子集
for (int subset = s; subset; subset = (subset - 1) & s) {
    // subset 是 s 的子集
}

lowbit 操作

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

常见技巧

判断第 i 位： (x >> i) & 1
设置第 i 位： x |= (1 << i)
清除第 i 位： x &= ~(1 << i)
翻转第 i 位： x ^= (1 << i)
统计 1 的个数： __builtin_popcount(x)

应用场景

1. 枚举子集

123456// 枚举所有子集
for (int mask = 0; mask < (1 << n); mask++) {
    for (int subset = mask; subset; subset = (subset - 1) & mask) {
        // subset 是 mask 的子集
    }
}

2. 状态压缩

12345// 用二进制表示状态
int state = 0;
state |= (1 << i);  // 选择第 i 个
state &= ~(1 << i); // 取消选择第 i 个
if (state & (1 << i)) { ... } // 判断第 i 个是否被选择

3. lowbit 应用

1234567891011121314// 树状数组
void update(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += c;
    }
}

int query(int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}

4. 用 bitset 表示超过 64 位的状态

当元素个数超过 64 时，整数已经无法装下整个状态，此时可以用 bitset：

1234bitset<100> state;            // 表示 100 个元素的选择状态
state.set(50);                // 选择第 50 个元素
if (state.test(50)) { ... }   // 判断第 50 个元素是否被选
cout << state.count() << endl; // 已选元素的个数

调试任何位运算代码时，随时 cout << bitset<32>(x) 观察中间结果，是排查位运算错误最快的方法。

考点分析

初赛考查方式

选择题： 位运算的应用
程序阅读： 理解位运算操作
编程题： 位运算应用

常见题型

用 bitset 查看变量的二进制表示、判断位运算结果
枚举子集
状态压缩
树状数组
bitset 表示超过 64 位的状态集合

例题精讲

例题 1：枚举子集

题目： 枚举集合 {1, 2, 3} 的所有子集。

解答：

123456789101112131415161718#include <iostream>
using namespace std;

int main() {
    int n = 3;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        cout << "{ ";
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                cout << i + 1 << " ";
            }
        }
        cout << "}" << endl;
    }
    
    return 0;
}

输出：

{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }

练习题

洛谷 P1896 互不侵犯

查看答案

思路：状压 DP，用二进制表示每行国王的放置状态。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <iostream>
using namespace std;

int n, k;
long long dp[10][100][1 << 10];
int cnt[1 << 10];

bool check(int state) {
    return (state & (state << 1)) == 0;
}

int count(int state) {
    int c = 0;
    while (state) {
        c += state & 1;
        state >>= 1;
    }
    return c;
}

int main() {
    cin >> n >> k;
    
    for (int i = 0; i < (1 << n); i++) {
        if (check(i)) {
            cnt[i] = count(i);
            dp[0][cnt[i]][i] = 1;
        }
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int s1 = 0; s1 < (1 << n); s1++) {
                if (!check(s1)) continue;
                for (int s2 = 0; s2 < (1 << n); s2++) {
                    if (!check(s2)) continue;
                    if (s1 & s2) continue;
                    if ((s1 << 1) & s2) continue;
                    if ((s1 >> 1) & s2) continue;
                    if (j + cnt[s1] <= k) {
                        dp[i][j + cnt[s1]][s1] += dp[i - 1][j][s2];
                    }
                }
            }
        }
    }
    
    long long ans = 0;
    for (int s = 0; s < (1 << n); s++) {
        ans += dp[n - 1][k][s];
    }
    
    cout << ans << endl;
    return 0;
}

洛谷 P2704 炮兵阵地

查看答案

思路：状压 DP，用二进制表示每行炮兵的放置状态，需要考虑两行的影响。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include <iostream>
using namespace std;

int n, m;
char grid[105][15];
int state[1 << 12], cnt[1 << 12], stateCount = 0;
int dp[105][1 << 10][1 << 10];

bool check(int s) {
    return (s & (s << 1)) == 0 && (s & (s << 2)) == 0;
}

int count(int s) {
    int c = 0;
    while (s) {
        c += s & 1;
        s >>= 1;
    }
    return c;
}

int main() {
    cin >> n >> m;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];
    
    for (int s = 0; s < (1 << m); s++) {
        if (check(s)) {
            state[stateCount] = s;
            cnt[stateCount] = count(s);
            stateCount++;
        }
    }
    
    // 第一行
    for (int i = 0; i < stateCount; i++) {
        int s = state[i];
        bool valid = true;
        for (int j = 0; j < m; j++) {
            if ((s & (1 << j)) && grid[0][j] == 'H') {
                valid = false;
                break;
            }
        }
        if (valid) dp[0][i][0] = cnt[i];
    }
    
    // 后续行
    for (int row = 1; row < n; row++) {
        for (int i = 0; i < stateCount; i++) {
            int s1 = state[i];
            bool valid1 = true;
            for (int j = 0; j < m; j++) {
                if ((s1 & (1 << j)) && grid[row][j] == 'H') {
                    valid1 = false;
                    break;
                }
            }
            if (!valid1) continue;
            
            for (int j = 0; j < stateCount; j++) {
                int s2 = state[j];
                if (s1 & s2) continue;
                
                for (int k = 0; k < stateCount; k++) {
                    int s3 = state[k];
                    if (s1 & s3) continue;
                    if (s2 & s3) continue;
                    
                    dp[row][i][j] = max(dp[row][i][j], dp[row - 1][j][k] + cnt[i]);
                }
            }
        }
    }
    
    int ans = 0;
    for (int i = 0; i < stateCount; i++)
        for (int j = 0; j < stateCount; j++)
            ans = max(ans, dp[n - 1][i][j]);
    
    cout << ans << endl;
    return 0;
}

洛谷 P3694 邦邦人的合唱

查看答案

思路：状压 DP，用二进制表示每个位置属于哪个组。

123456789101112131415161718192021222324252627282930313233343536#include <iostream>
using namespace std;

int n, m;
int a[105];
int dp[1 << 16];

int main() {
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) cin >> a[i];
    
    // 预处理：计算每个状态的逆序对数
    for (int s = 0; s < (1 << n); s++) {
        int cnt[16] = {0};
        for (int i = 0; i < n; i++) {
            if (s & (1 << i)) {
                for (int j = 0; j < i; j++) {
                    if (!(s & (1 << j)) && a[j] > a[i]) {
                        dp[s]++;
                    }
                }
            }
        }
    }
    
    // DP
    for (int s = 0; s < (1 << n); s++) {
        for (int sub = s; sub; sub = (sub - 1) & s) {
            dp[s] = min(dp[s], dp[sub] + dp[s ^ sub]);
        }
    }
    
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}

易错点

⚠️ 注意：

枚举子集时要注意边界

lowbit 操作是树状数组的基础

状态压缩要注意状态数

位运算进阶是状压 DP 的基础

第 0 位在二进制串的最右边，bitset<N>(x) 输出时高位在左、低位在右，不要把左右方向看反

bitset<N>(x) 只保留 x 的低 N 位，超出的高位会被丢弃；模板参数 N 必须是编译期常量，不能用变量

位运算进阶

概念讲解

用二进制的眼光看变量

bitset：把变量"打印"成二进制

bitset 作为容器：常用操作

枚举子集

lowbit 操作

常见技巧

应用场景

1. 枚举子集

2. 状态压缩

3. lowbit 应用

4. 用 bitset 表示超过 64 位的状态

考点分析

初赛考查方式

常见题型

例题精讲

例题 1：枚举子集

练习题

易错点

练习完成

恭喜完成学习！

提示

题目反馈