bitset 常用函数笔记
一、概述
std::bitset 是 C++ 标准库中固定大小的位集合容器，以 bit 为单位存储数据，空间效率极高，支持丰富的位运算操作。
- 头文件：
#include <bitset>
- 核心特点：大小
N 必须是编译期常量，不能动态改变
- 下标规则：从右往左编号，最右侧为第 0 位
二、定义与构造
| 写法 |
说明 |
bitset<N> bs; |
构造大小为 N 的 bitset，所有位初始为 0 |
bitset<N> bs(val); |
用无符号整数 val 初始化 |
bitset<N> bs(str); |
用 01 字符串 str 初始化 |
bitset<N> bs(str, pos, len); |
从字符串第 pos 位开始取 len 个字符初始化 |
示例：
bitset<8> b1; // 00000000
bitset<8> b2(10); // 00001010
bitset<8> b3("1010"); // 00001010
三、常用成员函数
1. 访问与查询
| 函数 |
功能 |
bs[i] |
访问第 i 位（可读可写） |
bs.test(i) |
返回第 i 位的值，越界抛异常 |
bs.count() |
返回 1 的个数 |
bs.size() |
返回总位数 N |
2. 修改操作
| 函数 |
功能 |
bs.set() |
所有位置 1 |
bs.set(i) |
第 i 位置 1 |
bs.set(i, val) |
第 i 位设为 val（0 或 1） |
bs.reset() |
所有位置 0 |
bs.reset(i) |
第 i 位置 0 |
bs.flip() |
所有位取反 |
bs.flip(i) |
第 i 位取反 |
3. 状态判断
| 函数 |
功能 |
bs.any() |
存在至少一个 1 则返回 true |
bs.none() |
全为 0 则返回 true |
bs.all() |
全为 1 则返回 true（C++11） |
4. 类型转换
| 函数 |
功能 |
bs.to_string() |
转为 string 类型的 01 串 |
bs.to_ulong() |
转为 unsigned long |
bs.to_ullong() |
转为 unsigned long long（C++11） |
四、支持的位运算符
bitset 可直接使用位运算符，操作简洁高效：
- 按位与：
a & b
- 按位或：
a | b
- 按位异或：
a ^ b
- 按位取反：
~a
- 左移：
a << n（右侧补 0）
- 右移：
a >> n（左侧补 0）
- 复合赋值：
&=, |=, ^=, <<=, >>=
五、注意事项
- 大小固定：
N 必须是编译期常量，不能用变量
- 下标方向：第 0 位是最右边（最低位），字符串最左对应最高位
- 越界行为：
operator[] 越界是未定义行为，test() 会抛异常
- 时间复杂度：单次位运算近似 O(N / 字长)，比手动位运算快很多
六、典型应用场景
- 状态压缩 DP（集合状态表示）
- 埃氏筛法优化（素数筛）
- 01 背包 bitset 优化
- 位图标记、布尔集合运算
