#include <bitset>
#include <bits/stdc++.h> // 竞赛直接这个cpp一、核心特性#
| 特性 | 说明 |
|---|---|
| 定长 | 长度 N 是模板参数,必须是编译期常量,不能运行期指定 |
| 压缩存储 | N 位约占 N/8 字节,比 vector<bool> 更规整、比 bool[N] 省 8 倍内存 |
| 下标方向 | b[0] 是最低位(最右边),b[N-1] 是最高位(最左边) |
| 整体位运算 | 支持 &、` |
| 无迭代器 | 不是标准容器,没有 begin(),遍历用下标 |
| 位运算复杂度 | O(N/64),不是 O(1),但常数极小 |
与替代品的对比:
| 方案 | 内存(N=10⁶) | 位运算 | 动态长度 |
|---|---|---|---|
bool a[N] |
1 MB | 无 | 可 VLA(非标准) |
vector<bool> |
125 KB | 无(需逐位) | 支持 |
vector<char> |
1 MB | 无 | 支持 |
bitset<N> |
125 KB | 整体并行 | 不支持 |
二、构造与初始化#
bitset<8> a; // 00000000,全 0
bitset<8> b(5); // 00000101,从整数低 8 位构造
bitset<8> c(string("1010")); // 00001010,从字符串构造
bitset<8> d("11001100"); // 11001100
// 字符串构造可指定起止和字符映射
bitset<8> e(string("xxoxxo"), 2, 4, 'o', 'x'); // 取子串,'o'→0 'x'→1
// 注意:N 必须是编译期常量
const int N = 1000;
bitset<N> f; // 正确
// int n; cin >> n; bitset<n> g; // 错误:n 不是编译期常量cpp长度不确定时的竞赛惯例:按题目数据范围上限开,如 bitset<200005>。
三、位访问与修改#
bitset<8> b;
b[3] = 1; // 置第 3 位为 1:00001000
b[0] = true; // 00001001
b.set(); // 全部置 1:11111111
b.set(3); // 只置第 3 位
b.set(3, 0); // 第 3 位置 0
b.reset(); // 全部清 0
b.reset(3); // 只清第 3 位
b.flip(); // 全部取反
b.flip(3); // 只翻转第 3 位
// 读取
bool x = b[3]; // 不检查越界
bool y = b.test(3); // 检查越界,越界抛 out_of_rangecpp四、统计与判断#
bitset<8> b("10110110");
b.count(); // 5,1 的个数,O(N/64),很快
b.size(); // 8,位数(编译期确定)
b.all(); // 是否全为 1 → false
b.any(); // 是否有 1 → true
b.none(); // 是否全为 0 → falsecppcount() 常用来统计答案,如筛法后的素数个数、背包可达状态数。
五、整体位运算(灵魂功能)#
bitset<8> a("10110110"), b("11000011");
auto c = a & b; // 10000010 按位与
auto d = a | b; // 11110111 按位或
auto e = a ^ b; // 01110101 按位异或
auto f = ~a; // 01001001 按位取反
a &= b; // 复合赋值都支持
a |= b; a ^= b;
// 移位:超出范围的位被丢弃,空位补 0
auto g = a << 2; // 左移 2 位(向高位,下标增大方向)
auto h = a >> 1; // 右移 1 位
a <<= 3; // 复合移位cpp移位方向与下标的关系:<< k 使原来的第 i 位变成第 i+k 位。01 背包正是靠这个性质。
所有位运算要求两个 bitset 长度相同(模板参数一致)。
六、转换与输入输出#
bitset<8> b("10110110");
string s = b.to_string(); // "10110110",高位在前
unsigned long x = b.to_ulong(); // 182,超出 unsigned long 范围会抛 overflow_error
unsigned long long y = b.to_ullong();
// 流输出:按高位到低位打印
cout << b; // 10110110
// 流输入:读入 0/1 字符序列
bitset<8> in;
cin >> in;cpp注意 to_string() 输出是高位在前,与下标顺序相反。
七、复杂度表#
| 操作 | 复杂度 |
|---|---|
b[i] / test / set(i) / reset(i) / flip(i) |
O(1) |
set() / reset() / flip() 全量 |
O(N/64) |
&、` |
、^、~、<<、>>` |
count / all / any / none |
O(N/64) |
to_string / to_ulong |
O(N) / O(1) |
空间:O(N/8) 字节。
八、竞赛经典应用#
1. 01 背包可行性(最经典的 bitset 加速)#
n 个物品各选或不选,问能否凑出重量 s。
普通 DP:f[i][j] 表示前 i 个物品能否凑出 j,复杂度 O(n·s) 且转移逐位。
bitset 优化:f[j] 表示能否凑出 j,第 i 个物品的加入 = 把可达状态左移 w 再或:
const int S = 100005;
bitset<S> f;
f[0] = 1; // 重量 0 可达
for (int i = 1; i <= n; i++) {
int w;
cin >> w;
f |= (f << w); // 选 w 后的所有可达状态并进来
}
cout << (f[s] ? "YES" : "NO");cpp复杂度从 O(n·s) 降为 O(n·s/64),n=s=10⁴ 级别轻松通过。
2. 传递闭包 / 可达性(Floyd 的 bitset 优化)#
n 个点有向图,求任意两点可达关系。
O(n³/64)。
const int N = 2005;
bitset<N> reach[N]; // reach[i][j]:i 能否到 j
// 读边
reach[u][v] = 1;
// Floyd:若 i 能到 k,则 i 能到 k 能到的所有点
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
if (reach[i][k])
reach[i] |= reach[k]; // 一行或运算代替内层 j 循环cpp内层 for j 被一次 |= 取代,加速 64 倍。
3. 筛法(省内存)#
const int N = 100000005;
bitset<N> notPrime;
for (long long i = 2; i * i < N; i++)
if (!notPrime[i])
for (long long j = i * i; j < N; j += i)
notPrime[j] = 1;
// 10⁸ 的标记数组用 bool 要 100MB,bitset 只要 12.5MBcpp4. 状态压缩替代(小规模状态集)#
// n <= 20 时也可用整数状压;n 在几十到几百时 bitset 更方便
bitset<64> state;
state.set(i); // 加入元素 i
state.reset(i); // 移除元素 i
state[i]; // 查询
(stateA & stateB).count(); // 交集大小,一行搞定cpp5. 子集交集大小 / 相似度#
// 每个集合用 bitset 表示,任意两集合的交、并、差规模都是一次位运算 + count
bitset<1005> s[105];
int common = (s[i] & s[j]).count();cpp九、与整数状压的选型#
| 需求 | 选择 |
|---|---|
| 状态数 ≤ 64,需要直接枚举子集、当数组下标 | unsigned long long 整数状压 |
| 状态数较大、需要整体位运算和移位 | bitset |
| 需要动态长度 | vector<bool> / 多个 uint64_t |
| 只需标记、不需位运算、长度动态 | vector<char> |
整数状压的特有技巧(bitset 没有):
x & -x:取最低位的 1;for (int s = mask; s; s = (s-1) & mask):枚举子集;__builtin_popcount(x):整数版 count。
bitset 里对应功能要自己循环或借助 _Find_first(MSVC 特有,竞赛可移植性差,不推荐)。
十、高频错误清单#
- 长度用运行期变量:
bitset<n>编译不过,N 必须是编译期常量。 - 下标方向搞反:
b[0]是最低位(最右),to_string()输出是高位在前。 - 以为位运算是
O(1):是O(N/64),但常数极小,N 很大时仍要算总账。 - 移位后超出范围的位被静默丢弃:
f << w高位溢出不会报错,背包容量要开够。 - 不同长度的 bitset 做位运算:模板参数不同是不同类型,编译错误。
- 大 bitset 定义成局部变量:
bitset<100000000>约 12.5MB,放栈上会爆栈,定义为全局变量。 to_ulong溢出:位数多且高位有 1 时抛overflow_error,不是静默截断。- 试图用迭代器或范围 for 遍历:bitset 不是容器,用下标循环。
十一、一页速记#
bitset<N> b; // N 编译期常量,全 0
bitset<N> b(5); // 从整数
bitset<N> b("1010"); // 从字符串
b[i]; b.test(i); // 读(0 是最低位)
b.set(i); b.reset(i); b.flip(i); // 改单个
b.set(); b.reset(); b.flip(); // 改全部
b.count(); b.any(); b.none(); b.all(); // 统计
a & b; a | b; a ^ b; ~a; // 位运算 O(N/64)
a << k; a >> k; // 移位,溢出丢弃
b.to_string(); b.to_ullong();
// 01 背包
f[0] = 1;
for (每个物品 w) f |= (f << w);
// 传递闭包
for k: for i: if (reach[i][k]) reach[i] |= reach[k];cpp五句口诀:
- 长度是模板参数,编译期定死;不确定就按数据范围上限开。
b[0]是最低位,to_string()高位在前——两个方向别搞混。- 位运算
O(N/64),用f |= f << w一行完成 01 背包转移。 - 大 bitset 放全局,别放栈上。
- 要动态长度用
vector<bool>,要子集枚举用整数状压,bitset 主打定长位并行。