位运算进阶

概念讲解

枚举子集

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

lowbit 操作

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

常见技巧

  1. 判断第 i 位： (x >> i) & 1
  2. 设置第 i 位： x |= (1 << i)
  3. 清除第 i 位： x &= ~(1 << i)
  4. 翻转第 i 位： x ^= (1 << i)
  5. 统计 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;
}

考点分析

初赛考查方式

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

常见题型

  • 枚举子集
  • 状态压缩
  • 树状数组

例题精讲

例题 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 }

练习题

  1. 洛谷 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;
}
  1. 洛谷 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;
}
  1. 洛谷 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;
}

易错点

⚠️ 注意：

  1. 枚举子集时要注意边界
  2. lowbit 操作是树状数组的基础
  3. 状态压缩要注意状态数
  4. 位运算进阶是状压 DP 的基础