常见用途

  • 用整型得每一位表示集合/状态(状态压缩/子集枚举)
  • 用异或解决[成对出现]类问题、前缀异或或计数子数组异或
  • 用lowbit在树状数组、枚举子集优化中快速操作
  • 用bitset做超快的背包/集合操作，常把o(n*S /word)变成非常快的位并行
  • 用位技巧做常数优化、逻辑判断(奇偶、是否是2的幂等)

tips

1
2
3
4
5
6
7
8
// 记得：对于超过 31 位的位运算用 1LL 或 1ULL
int test = (mask & (1 << k));    // 测试第 k 位 (0-indexed)
mask |= (1 << k);                // 将第 k 位置 1
mask &= ~(1 << k);               // 将第 k 位清 0
mask ^= (1 << k);                // 切换（toggle）第 k 位
int lowbit = mask & -mask;       // 取最低位 1（lowbit），mask != 0
int cnt = __builtin_popcount(mask);      // 32-bit 的 1 个数
int cnt64 = __builtin_popcountll(x);     // 64-bit
  • 1<<k的类型是int;如果k>=31(在32位int)会出现问题->用1LL<<k或1ULL<<k
  • 左移超出类型宽度是UB(underfined behavior)
  • lowbit依赖二补码，C++/Java可用

use

判断奇偶

1
2
if(x&1)std::cout<<"奇数";
else std::cout<<"偶数";

判断是否为2的幂

x>0,2的幂必须是正整数(1,2,4,8,…),首先排除x<=0的情况
一个2的幂在二进制中只有一个1，其余全是0，x-1会把唯一的1变成0,同时右边的所有位都变成1

1
2
3
bool isPowerOfTwo(int x){
    return x>0 && (x&(x-1))==0;
}

也可以使用__builtin_popcount(x)统计x中1的个数也可以用来判断是否为2的幂
__builtin_popcount(x)只适用于unsigned int，long long需要使用__builtin_popcountll(x)
C++20可以使用std::popcount((unsigned)x)

快速乘除

1
2
x<<k //乘2^k
x>>k //除2^k(向下取整)

博弈论

  • Nim博弈、石子游戏常用异或：
    • 若所有堆的石子数异或和为0->先手必败
    • 否则先手必胜

汉明距离

计算两个整数的汉明距离
汉明距离=异或后结果的二进制中1的个数

1
int hamming(int a, int b) { return __builtin_popcount(a ^ b); }

枚举mask的所有非空子集

若要包含0：在循环外单独处理0
复杂度：对于固定mask，迭代其子集的复杂度是O(2^{popcount(mask)})。总体常见用于n<=20的 DP/枚举场景。
应用场景：状压 DP 中转移、枚举某一集合的划分、分块枚举。

1
2
3
for (int s = mask; s; s = (s - 1) & mask) {
    // s 遍历 mask 的所有非零子集（包含 mask 本身，不包含 0）
}

状态DP

典型问题：TSP/Hamilton 路径/集合覆盖（n ≤ 16~20）
注意内存：O(n*2^n)，若 n=20，约20* 1,048,576 ≈ 20M 状态，整型可行；n>20 则需其他方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//模板（求最短 Hamilton 路）：
const int INF = 1e9;
int n;
vector<vector<int>> dist; // n x n
int N = 1 << n;
vector<vector<int>> dp(N, vector<int>(n, INF));
dp[1 << start][start] = 0;
for (int mask = 0; mask < N; ++mask) {
    for (int i = 0; i < n; ++i) if (dp[mask][i] < INF) {
        for (int j = 0; j < n; ++j) if (!(mask & (1 << j))) {
            dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j]);
        }
    }
}

异或操作

找唯一数（所有数出现两次，只有一个出现一次）

1
2
int ans=0;
for(int x:a)ans^=x;

找两个只出现一次的数（其余出现两次）

1
2
3
4
5
6
7
8
int xorsum = 0;
for (x : a) xorsum ^= x;
int low = xorsum & -xorsum;
int a1 = 0, a2 = 0;
for (x : a) {
    if (x & low) a1 ^= x;
    else a2 ^= x;
}

子数组异或等于 K（前缀 xor + hash）
对于计数 pairsai ^ aj == k（i < j）：用哈希表统计出现次数：ans += cnt[ai ^ k]，然后 cnt[ai]++

1
2
3
4
5
6
7
8
9
long long ans = 0;
unordered_map<int,int> cnt;
cnt[0] = 1;
int px = 0;
for (int x : a) {
    px ^= x;
    ans += cnt[px ^ K];
    cnt[px]++;
}

SOS DP

用途：给 f[mask]，想要对每个 mask 求 g[mask] = sum_{s ⊆ mask} f[s](或类似的 OR-convolution 预处理)
若想枚举超集、或做反向变换，方向和条件稍变。SOS DP 常用于子集卷积、按 OR/AND 的快速预处理

1
2
3
4
5
6
7
8
9
//模板
int n; // bit 数
int N = 1 << n;
vector<int> g = f; // copy
for (int i = 0; i < n; ++i) {
    for (int mask = 0; mask < N; ++mask) {
        if (mask & (1 << i)) g[mask] += g[mask ^ (1 << i)];
    }
}

bitset加速，位并行

0/1 背包（sum ≤ S），用 bitset 能把复杂度变得非常
bitset 的宽度必须在编译期固定（bitset<100001>），或用动态的 vector<unsigned long long> 实现位运算。它能把常数非常降低（机器字并行）
应用：多次子集和/大范围背包、快速集合运算、用于转移的并行化

1
2
3
4
5
const int S = 100000;
bitset<S+1> bs;
bs[0] = 1;
for (int w : weights) bs |= (bs << w);
// then bs[s] 表示是否能凑出和 s

lowbit在树状数组与枚举中的应用

树状数组 add/sum 中用 lowbit(x) = x & -x
把x的最低1位删除：x &= x - 1（常用于统计/循环最低位的删除，复杂度按 1 的个数）

Gray Code(用于增量更新)

Gray code 定义：g(i) = i ^ (i >> 1)，两个相邻 Gray 值只差 1 位。用于需要按一位变换来做状态更新的 DP（例如滑窗维护时增量更新集合信息），能把每一步转移变成常数时间修改