专门处理二进制位的容器——每个元素只占 1 个 bit，处理位运算时极其高效。
bitset 是一个专门处理二进制位的容器。它的每一个元素只占 1 个 bit（而不是 1 个字节），处理位运算时极其高效。使用前需引入 <bitset> 头文件。
bool 数组里 1 个字节（8 bit）。8 个元素的 bitset 实际只占用 1 个字节的内存，vector<bool> 也有类似的压缩存储，但 bitset 的位运算接口更直接好用。bitset<N> 的大小 N 必须是编译期常量，定义好之后不能再改变长度——这点和 array 类似，跟可以动态变长的 vector 不同。| 1 | #include <bitset> |
| 2 | using namespace std; |
| 3 | |
| 4 | int main() |
| 5 | { |
| 6 | bitset<8> b1; // 全部初始化为 0：00000000 |
| 7 | bitset<8> b2("10101010"); // 用字符串初始化：10101010 |
| 8 | bitset<8> b3(10); // 用整数初始化：10 的二进制是 00001010 |
| 9 | |
| 10 | cout << b2 << endl; // 直接 cout 输出：10101010 |
| 11 | |
| 12 | return 0; |
| 13 | } |
bitset 可以直接用 cout 输出，会自动打印成二进制字符串的形式——不需要手动转换，这点比手写位运算方便很多。bitset 提供了一套读、改单个 bit 的成员函数，比手写 (n >> i) & 1 之类的位运算表达式更直观。
| 函数 | 功能 | 返回值 / 效果 |
|---|---|---|
| .count() | 统计有多少位是 1 | size_t |
| .test(i) | 查询第 i 位是 0 还是 1 | bool |
| .set(i) | 把第 i 位设为 1 | 无 |
| .set(i, v) | 把第 i 位设为 v（0 或 1） | 无 |
| .reset(i) | 把第 i 位设为 0 | 无 |
| .flip(i) | 把第 i 位翻转（0↔1） | 无 |
| .flip() | 把全部位翻转 | 无 |
| .any() | 是否至少有一位是 1 | bool |
| .none() | 是否全部位都是 0 | bool |
| .size() | 返回 bitset 的总位数（即 N） | size_t |
| .to_string() | 转换成字符串 | string |
| .to_ulong() | 转换成 unsigned long | unsigned long |
| 1 | bitset<8> b("10101010"); |
| 2 | |
| 3 | cout << b.count() << endl; // 4——有 4 个 1 |
| 4 | cout << b.test(0) << endl; // 0——第 0 位是 0 |
| 5 | cout << b.test(1) << endl; // 1——第 1 位是 1 |
| 6 | |
| 7 | b.set(0, 1); // 把第 0 位设为 1 |
| 8 | b.reset(2); // 把第 2 位设为 0 |
| 9 | b.flip(); // 全部翻转（0 变 1，1 变 0） |
bitset 的下标 从右往左数，从 0 开始——和 vector、数组的下标方向相反。b[0] 是最右边（最低位），不是最左边。打印出来的字符串顺序是"高位在左"，但 .test() / .set() 的下标是从右边的低位开始数的，刚学的时候容易搞反。bitset 支持和整数一样的位运算符 &（与）、|（或）、^（异或）、~（取反），写法和数学符号一致，但作用在每一位上：
| 1 | bitset<8> a("1100"), c("1010"); |
| 2 | |
| 3 | cout << (a & c) << endl; // 按位与：00001000 |
| 4 | cout << (a | c) << endl; // 按位或：00001110 |
| 5 | cout << (a ^ c) << endl; // 按位异或：00000110 |
int 最多 32 / 64 位，bitset 可以开到几千甚至几万位，并且 & / | / ^ 这些运算在底层是按"机器字长"批量处理的（比如 64 位一次），比逐位循环判断快得多。常用于状态压缩 DP、筛法优化（如埃氏筛配合 bitset 标记）等场景。| 1 | #include <iostream> |
| 2 | #include <bitset> |
| 3 | using namespace std; |
| 4 | |
| 5 | int main() |
| 6 | { |
| 7 | bitset<8> b("10101010"); // 8位二进制：10101010 |
| 8 | cout << b << endl; // 输出：10101010 |
| 9 | cout << b.count() << endl; // 输出：4——有几个 1 |
| 10 | cout << b.test(0) << endl; // 输出：0——第 0 位是 0 |
| 11 | cout << b.test(1) << endl; // 输出：1——第 1 位是 1 |
| 12 | |
| 13 | b.set(0, 1); // 把第 0 位设为 1 |
| 14 | b.reset(2); // 把第 2 位设为 0 |
| 15 | b.flip(); // 全部翻转（0 变 1，1 变 0） |
| 16 | |
| 17 | // 位运算 |
| 18 | bitset<8> a("1100"), c("1010"); |
| 19 | cout << (a & c) << endl; // 按位与：1000 |
| 20 | cout << (a | c) << endl; // 按位或：1110 |
| 21 | cout << (a ^ c) << endl; // 按位异或：0110 |
| 22 | return 0; |
| 23 | } |
把本节出现过的方法按用途归类汇总，写代码时可以直接当参考卡用。
| 方法 / 写法 | 分类 | 作用 |
|---|---|---|
| bitset<N> b | 定义 | 定义 N 位、全为 0 的 bitset |
| bitset<N> b("...") | 定义 | 用 0/1 字符串初始化 |
| bitset<N> b(x) | 定义 | 用整数 x 的二进制初始化 |
| b[i] | 访问 | 访问第 i 位（从右往左，从 0 开始） |
| .test(i) | 查询 | 第 i 位是否为 1 |
| .count() | 查询 | 有多少位是 1 |
| .any() / .none() | 查询 | 是否有 1 / 是否全为 0 |
| .size() | 查询 | 总位数 N |
| .set(i) / .set(i,v) | 修改 | 第 i 位设为 1 / 设为 v |
| .reset(i) / .reset() | 修改 | 第 i 位设为 0 / 全部清零 |
| .flip(i) / .flip() | 修改 | 第 i 位翻转 / 全部翻转 |
| & / | / ^ / ~ | 位运算 | 与 / 或 / 异或 / 取反 |
| << / >> | 位运算 | 整体左移 / 右移 |
| .to_string() | 转换 | 转成 string |
| .to_ulong() / .to_ullong() | 转换 | 转成 unsigned (long) long |
bool 变量或数组反而更直观。