2026-02-06

前言

bitset 是一种空间开销极小，时间开销也极小的一种类似于 bool 类型的方法。相对于 bool 的每一个变量占用一个字节，bitset 每一个变量只占用一个位（1字节 = 8位），所以空间占用极小，访问也特别快，适合用于卡常。

本文只讲一些常见的 bitset 函数和操作，其他的神秘函数和神秘操作一概不提。

定义方式

bitset 包含在头文件 #include<bitset> 里，当然万能头自带。

定义方式：

bitset<数组大小> 变量名(初始化值);

其中，程序会按“初始化值”的对应二进制位初始化 bitset，举个例子：

bitset<100005> vis(2)

这里 2 的二进制是 10，所以对于我们定义的 $vis$ 数组中，只有第二位被赋值为了 1，其余都是 0。

再举个例子：

bitset<8> vis(0xFF)

这个 0xFF 是十六进制，转化为二进制为 11111111，所以这里 $vis$ 被赋值为了 11111111。

当然 (初始化值) 这部分可以省略，就默认初始化为 0。

bitset 还可以从字符串初始化，但是真的有人会用吗？

访问方式

bitset 有两种访问方式：

变量名[下标];

和

变量名.test(下标);

OI 建议使用第一种，因为第二种会多一些检查机制，速度稍慢，不过区别不大，但是第一种更符合一般的数组调用风格。

修改方式

bitset 依旧有两套元素修改方式。

第一种就是正常的数组修改方式，不多说。

第二种：

变量名.set(下标)      // 赋值为 1
变量名.reset(下标)    // 赋值为 0
// 这两个函数的其他用处
变量名.set()          // 将所有位设置为 1
变量名.reset()        // 将所有位设置为 0

显然第二种方法还是没有第一种速度快，依旧推荐使用第一种。

还有取反操作：

变量名.flip()         // 所有元素取反，和 变量名 = ~变量名 效果相同
变量名.flip(下标)     // 下标位置取反

哦对了，在对整个 bitset 赋值的时候不要使用这种模式：

变量名 = (1 << 31);

但是这样是可以的：

变量名 = (1UL << 31);

两者的区别在于第二种声明了无符号类型，如果你使用第一种的话，程序会进行一个叫 符号扩展 的操作，实际上这个 bitset 的 32 到 64 位都被赋值为了 1。

如果是这样的：

变量名 = (n << 31);

参考上文，只要 n 是无符号类型就没问题。

元素统计

变量名.count()       // 查询数组中 1 的个数，时间复杂度要看具体的 CPU、优化参数和编译器决定，反正肯定远远小于 O(n)，大概是 O(n) 的几十分之一
变量名.any()         // 判断是否存在 1
变量名.none()        // 判断是否所有元素都是 0
变量名.all()         // 判断是否所有元素都是 1

这里注意到 变量名.count() 的返回值类型是 size_t，当然你用 int 或 long long 或 无符号类型 也没问题。

类型转换

bitset 支持一些基础的类型转换：

变量名.to_string()        // 将所有储存的值转化为 string 类型，也就是一个 01 串
变量名.to_ulong()         // 将储存的值按高低位转化为 unsigned long 类型，至于 unsigned long 的储存范围需要参考操作系统，所以不推荐使用，我在下文会忽略掉它。
变量名.to_ullong()        // 将储存的值按高低位转化为 unsigned long long 类型。

这里转化为 unsigned long long 类型的规则：

如果在转换时 bitset 里面除去前 64 位，其它位还有 1 的话程序会抛出异常。
超过 64 位的部分没有 1 会被忽略，有 1 就逝了。

至于转换的速度嘛，.to_string() 是 $O(n)$，.to_ullong() 是严格小于 $O(n)$ 的，和 .count() 是一个等级。

所以好消息是我们可以使用 bitset 进行整数运算，但是需要先转化。这样唯一的优势就是可以控制位的数量，比如 int 太小存不下但是 long long 爆空间这种情况，当然我觉得这种情况并不常见。

操作支持

bitset 支持所有位运算，会逐位进行操作。

bitset 可以直接被 cin 读入，但是 scanf 不行，读入规则：

读入内容是一个 01 串。
如果读取过程中碰到不是 0 或 1 的字符会自动停止读入。
读入的内容会被赋值到低位，比如一个 10 位的 bitset，读入内容为 110011，那么结束读入后这个 bitset 的值就是 0000110011。

bitset 也可以直接被 cout 输出，内容是所有位的元素，如果要只输出一部分请自行写循环，或者转化为 string 类型用 .substr() 函数输出。

变量名._Find_first()     // 查找第一个 1，括号里面不添加参数
变量名._Find_next(n)    // 查找 n 位置之后的第一个 1，必须加参数
变量名.size()            // 返回 bitset 大小，有用吗？

如果要遍历所有 1 的话，请使用位运算优化的方式，当然如果你要 $O(n)$ 枚举我也不拦你。

其它用处

1

将一个数 $n$ 转化为二进制：

bitset<转化后二进制位数>(n);

~~早知道有这玩意谁还手动写 while 循环啊~~

2

用于优化 DP，比如状压DP 和 01背包，特别是 01背包，可以大幅缩减时间的使用。

这么简单，就不给例子了。

反正只需保存两种状态的东西都可以使用 bitset 进行时间与空间优化，什么素数筛法啊，搜索啊都可以使用，并且推荐使用。

小结

bitset 空间使用小，访问快，操作丰富，碾压 bool，除非请出 STL 大军，因为 bitset 不支持动态空间，当然如果你这样写的话我也没办法：

vector<bitset<1>> 变量名;

如果还有什么疑问或者建议就发消息告诉我吧，我能接收到就可以。

Bitset的使用方法

前言