麦地

Back

#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("10110110");

b.count();         // 5,1 的个数,O(N/64),很快
b.size();          // 8,位数(编译期确定)

b.all();           // 是否全为 1 → false
b.any();           // 是否有 1   → true
b.none();          // 是否全为 0 → false
cpp

count() 常用来统计答案,如筛法后的素数个数、背包可达状态数。


五、整体位运算(灵魂功能)#

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.5MB
cpp

4. 状态压缩替代(小规模状态集)#

// n <= 20 时也可用整数状压;n 在几十到几百时 bitset 更方便
bitset<64> state;
state.set(i);            // 加入元素 i
state.reset(i);          // 移除元素 i
state[i];                // 查询
(stateA & stateB).count(); // 交集大小,一行搞定
cpp

5. 子集交集大小 / 相似度#

// 每个集合用 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 特有,竞赛可移植性差,不推荐)。


十、高频错误清单#

  1. 长度用运行期变量:bitset<n> 编译不过,N 必须是编译期常量。
  2. 下标方向搞反:b[0] 是最低位(最右),to_string() 输出是高位在前。
  3. 以为位运算是 O(1):是 O(N/64),但常数极小,N 很大时仍要算总账。
  4. 移位后超出范围的位被静默丢弃:f << w 高位溢出不会报错,背包容量要开够。
  5. 不同长度的 bitset 做位运算:模板参数不同是不同类型,编译错误。
  6. 大 bitset 定义成局部变量:bitset<100000000> 约 12.5MB,放栈上会爆栈,定义为全局变量。
  7. to_ulong 溢出:位数多且高位有 1 时抛 overflow_error,不是静默截断。
  8. 试图用迭代器或范围 for 遍历:bitset 不是容器,用下标循环。

十一、一页速记#

五句口诀:

  1. 长度是模板参数,编译期定死;不确定就按数据范围上限开。
  2. b[0] 是最低位,to_string() 高位在前——两个方向别搞混。
  3. 位运算 O(N/64),用 f |= f << w 一行完成 01 背包转移。
  4. 大 bitset 放全局,别放栈上。
  5. 要动态长度用 vector<bool>,要子集枚举用整数状压,bitset 主打定长位并行。
Comment seems to stuck. Try to refresh?✨