是什么
bitset 是 C++ 标准库提供的固定大小的位序列容器，用于高效存储和操作二进制位。（这么高级）
核心要点：
- 大小在编译期确定，通过模板参数 N 指定
- 每个位只占 1 bit 内存，远优于 bool 数组（每个占 1 字节）
（这么小！） - 原生支持位运算（与、或、异或、取反、左移、右移）
（哇塞）
本质理解：可以把它看作一个固定长度的二进制数，同时支持数组式的位访问和数值式的位运算。
怎么实现
1. 基本用法
#include<bits/stdc++.h>
using namespace std;
int main() {// 初始化bitset<8> b1; // 00000000，默认全0bitset<8> b2(42); // 00101010，从整数构造bitset<8> b3("1010"); // 00001010，从字符串构造，注意从右向左填充bitset<8> b4(0b11110000); // 11110000，C++14起支持二进制字面量// 访问与修改b1[0]=1; // 设置最低位为1，无边界检查b1.set(2); // 将第2位设为1，从0开始计数b1.reset(0); // 将第0位设为0b1.flip(3); // 翻转第3位，0变1，1变0bool bit=b1.test(5); // 访问第5位，有边界检查，越界抛异常//b.test(i);访问第i位的值（从0开始计数），返回bool；有边界检查为1/0，越界抛out_of_range异常// 批量操作b1.set(); // 全部置1b1.reset(); // 全部置0b1.flip(); // 全部取反// 查询size_t cnt=b1.count(); // 返回1的个数size_t sz=b1.size(); // 返回总位数，即模板参数Nbool has_1=b1.any(); // 是否有任意位为1bool all_0=b1.none(); // 是否全部为0bool all_1=b1.all(); // 是否全部为1，C++11起// 转换string s=b1.to_string(); // 转为"0101..."字符串unsigned long val=b1.to_ulong(); // 转为整数，超出范围抛异常unsigned long long val64=b1.to_ullong();return 0;
}
2. 位运算操作
bitset<4> a(0b1010); // 1010
bitset<4> b(0b1100); // 1100auto r1=a&b; // 1000，按位与
auto r2=a|b; // 1110，按位或
auto r3=a^b; // 0110，按位异或
auto r4=~a; // 0101，按位取反
auto r5=a<<1; // 0100，左移，低位补0
auto r6=a>>1; // 0101，右移，高位补0
3. 示例：埃氏筛法
#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
bitset<N> prim;
prim.set(); // 先全部置1
prim.reset(0); // 0不是素数
prim.reset(1); // 1不是素数for(int i=2;i*i<N;i++){if(prim.test(i))// 如果i当前仍被标记为素数（未被之前的合数标记覆盖）for(int j=i*i;j<N;j+=i) is_prime.reset(j); // 标记合数
}
// 此时 prim.test(n) 为1表示n是素数
4. 内部实现原理（理解层面）
bitset 的典型内部实现是使用一个或多个无符号整数数组（如 unsigned long 数组）来存储位，每个元素充当一个"位桶"。
- 访问第 i 位时：先定位到第
i / word_bits个数组元素，再通过i % word_bits定位到具体位 - 位运算（如与运算）则是对底层数组逐元素执行相应运算
- 编译器在开启优化时，这些操作通常会被内联展开，性能很高
标准库并未规定具体实现方式，各编译器可能略有差异，但上述原理是通用的。
三、TIPS
优点：
- 内存极省：8个位只占1字节
- 代码简洁：位运算和批量操作一行搞定
- 性能高：无动态内存分配，完全栈上或静态存储
- 类型安全：编译期检查大小
注意事项：
| 问题 | 说明 | 建议 |
|---|---|---|
| 大小必须编译期确定 | bitset<n> 中的 n 必须是 constexpr/const |
需要动态大小用 std::vector<bool> 或 Boost 的 dynamic_bitset |
| 下标不检查边界 | 越界访问是未定义行为 | 不确定索引时用 test(pos) |
| 字符串长度不能超 | 构造时字符串长度大于 N 会抛异常 | 确保字符串不超过模板参数 |
| 整数转换有范围限制 | to_ulong() 对超过 unsigned long 范围的 bitset 抛异常 |
确认位数不超过64再用 |
| vector |
vector |
固定大小首选 bitset，动态大小用 Boost |
与 vector<bool> 对比速查：
| 场景 | 推荐 |
|---|---|
| 大小固定且编译期已知 | bitset |
| 大小运行时动态变化 | vector<bool> |
| 需要容器特性（迭代器、取地址等） | 避免用 vector |
| 大小非常大（百万级）且动态 | Boost 的 dynamic_bitset |
个人补充：
- 用 bitset 做权限管理（每位代表一种权限）非常方便
- 在网络协议解析、寄存器操作等底层编程中很实用
- 算法题中，bitset 做状态压缩 DP 时能显著降低内存
- bitset 的左移和右移是逻辑移位，移出的位直接丢弃，空位补0，不是循环移位
Bitset 优化DP
好问题，为什么bitset可以优化dp？ （我不道啊）
为什么 bitset 可以优化 DP
一句话回答：因为 bitset 用一条位运算指令代替了原本需要循环遍历所有状态的操作。
拆开来说：
-
DP 状态是布尔值
大多数背包、子集和类 DP，状态只有两种：可达/不可达、1/0。这正好对应二进制位的 1 和 0。 -
状态转移本质是集合操作
比如"添加一个重量为 \(w\) 的砝码"：- 原来的可达重量是集合 \(A\)
- 加上这个砝码后，新可达重量是集合 \(A+w\)（A 中每个元素加 w）
- 最终状态是 \(A \cup (A + w)\)
这个操作对应到 bitset：dp|(dp<<w)，一次或运算 + 一次移位就完成了。
-
CPU 位运算的并行性
普通 DP 需要循环遍历每个重量：for (int k=1000;k>=w;k--) if (dp[k-w]) dp[k]=1;bitset 的
dp<<w在底层是对 64 位整数的移位操作，一条指令同时处理 64 个 bit，相当于循环 64 次。所以复杂度从 \(O(n)\) 降为 \(O(n/64)\)。
原来是这样。
结论
bitset 能优化 DP 是因为：它把 DP 的"遍历状态逐个更新"变成了 CPU 原生支持的"批量位运算"，利用了硬件的并行能力。
例题：P2347
为什么这道题可以用 bitset 优化
这道题是多重背包可行性问题，判断哪些重量可以被凑出，每个重量只有两种状态：可达或不可达，正好对应二进制位的 1 和 0。
用 bitset 的核心优势：
-
状态压缩：用一个二进制数的第 \(i\) 位表示重量 \(i\) 是否可达，1000 个重量只需要 1000 个 bit，约 \(125\) 字节
-
集合运算：添加一个重量为 \(w\) 的砝码，相当于把当前所有可达重量整体"平移" \(w\) 个单位
- 平移操作：
dp << w，一次移位同时处理所有位 - 合并操作：
dp |= (dp << w)，一次或运算完成"选或不选"的合并
- 平移操作：
-
位运算替代循环：普通 DP 需要遍历 0~1000 逐个更新，bitset 用一条 CPU 指令同时操作 64 位甚至更多，效率提升约 64 倍
-
代码简洁：核心转移只有一行
dp |= dp << w[i]，原本需要两层循环的 DP 用位运算表达得非常清晰
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10],w[10]={0,1,2,3,5,10,20}; // w[i]：第 i 种砝码的重量
bitset<1010> s; // s 二进制第 i 位 = 1 表示重量 i 可达
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);for(int i=1;i<=6;i++) cin>>a[i]; // 输入每种砝码的数量s[0]=1; // 重量 0 可达（不放任何砝码）for(int i=1;i<=6;i++) // 遍历 6 种砝码for(int j=0;j<a[i];j++) // 逐枚处理第 i 种砝码，保证每个砝码只用一次s|=s<<w[i]; // 核心转移：当前可达重量整体增加 w[i]g，再与原状态合并cout<<"Total="<<s.count()-1; // s.count() 返回所有可达重量的个数，减去重量 0return 0;
}
哦。
注：部分内容来源于某只鲸鱼（我太菜了）。