bitset 位集

读完能做什么

• 能创建固定位数的 bitset，说出每一位是 0 还是 1，并算出一共有几个 1。
• 能用 set、reset、flip 打开、关闭、翻转某一位，也能一次处理全部位。
• 能分清“显示字符串的左端是高位、右端是第 0 位”，并手算按位与、按位或的结果。
• 能说出位下标越界时 test 抛异常、operator[] 不检查，以及移位会丢弃越出固定宽度的位。

为什么需要它

很多问题可以用“一串开关”来记录状态：某个数出现过没有、某个人到场没有、某几个选项选中没有。用 bool 数组当然也行，但每个开关其实只需要 1 个二进制位，而 bool 通常要占 1 个字节；bitset 把这些位打包在一起，更省内存，还能整块做按位运算。

比如“用一个 8 位串记录 8 个灯的开灭”，用数组要写循环逐个设置；如果把它看成一个整体，就能用 set、flip 一次操作某一位，用 &、| 一次合并两组开关。标准库为此提供了 bitset：一个位数固定、每一位只存 0/1 的小容器。

它是什么

一句话：bitset<N> 是固定 N 位的二进制开关，每一位是 0 或 1。

几个必须就地看懂的概念：

位数写死在模板尖括号里。 bitset<8> 表示“8 位”，bitset<32> 表示“32 位”。这里的 <8> 是模板参数，创建之后位数不能改，不能像 vector 那样 push_back。这是 bitset 和 vector<bool> 的主要区别。

位下标从 0 开始，0 是最右边那位。 第 0 位是最低位，在显示字符串的最右端；位数减 1 是最高位，在最左端。

显示字符串的方向。 用字符串构造时，字符串从左到右对应“从高位到低位”。以 bitset<8>("00000101") 为例：

graph LR
    L["字符串左端 高位 下标 7"] --> R["字符串右端 低位 第 0 位"]

所以 "00000101" 里，从左往右第 6 个字符是第 2 位，最后一个是第 0 位。字符串的读法和位下标的读法是反的，这是最容易看错的地方。

operator[] 与 test。 b[i] 像数组下标一样读写第 i 位；b.test(i) 只读第 i 位，并且会检查范围。区别见后面“哪里容易错”。

适用场景：位数固定、需要逐位操作或整块按位运算。使用时要 #include <bitset>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

最小可运行示例

用字符串 "00000101" 构造一个 8 位 bitset，读出几位并数 1 的个数：

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> b("00000101");

    cout << "内容：" << b << '\n';
    cout << "第 0 位：" << b[0] << '\n';
    cout << "第 1 位：" << b[1] << '\n';
    cout << "第 2 位：" << b[2] << '\n';
    cout << "1 的个数：" << b.count() << '\n';
    return 0;
}

输出：

内容：00000101
第 0 位：1
第 1 位：0
第 2 位：1
1 的个数：2

逐行看：

• bitset<8> b("00000101"); 用 8 个字符的字符串构造。字符串右端是第 0 位，所以第 0 位是 1、第 2 位是 1，其余都是 0。
• cout << b 直接打印整个 bitset，输出 00000101，左边是高位、右边是第 0 位。
• b[0]、b[1]、b[2] 是位下标访问，分别得到 1、0、1。
• b.count() 数出 1 的个数，这里是 2。

一步步看变化

沿 "00000101" 依次做三次单位操作：

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> b("00000101");

    b.set(1);       // 第 1 位置 1
    cout << "set(1) 后：" << b << '\n';

    b.reset(2);     // 第 2 位清 0
    cout << "reset(2) 后：" << b << '\n';

    b.flip(0);      // 第 0 位翻转
    cout << "flip(0) 后：" << b << '\n';
    return 0;
}

输出：

set(1) 后：00000111
reset(2) 后：00000011
flip(0) 后：00000010

对照表格逐步核对：

• set(1) 把第 1 位从 0 改成 1，00000101 → 00000111。
• reset(2) 把第 2 位从 1 改成 0，00000111 → 00000011。
• flip(0) 把第 0 位从 1 翻成 0，00000011 → 00000010。

逐项扩展核心操作

按位与、按位或

bitset 支持整块的按位运算。把 00000101 和 00000011 逐位对齐：

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> a("00000101");
    bitset<8> b("00000011");

    cout << "a & b：" << (a & b) << '\n';
    cout << "a | b：" << (a | b) << '\n';
    return 0;
}

输出：

a & b：00000001
a | b：00000111

按位与 00000101 & 00000011 得到 00000001：只有第 0 位两边都是 1。按位或 00000101 | 00000011 得到 00000111：第 0、1、2 位至少有一边是 1。运算结果的位数不变，仍是 8 位。

test、any、none、all、count

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> b("00000101");

    cout << "test(0)：" << b.test(0) << '\n';
    cout << "any()：" << b.any() << '\n';
    cout << "none()：" << b.none() << '\n';
    cout << "all()：" << b.all() << '\n';
    cout << "count()：" << b.count() << '\n';
    cout << "size()：" << b.size() << '\n';

    b.set();        // 全部置 1
    cout << "set() 后：" << b << "，all()：" << b.all() << '\n';

    b.reset();      // 全部置 0
    cout << "reset() 后：" << b << "，none()：" << b.none() << '\n';
    return 0;
}

输出：

test(0)：1
any()：1
none()：0
all()：0
count()：2
size()：8
set() 后：11111111，all()：1
reset() 后：00000000，none()：1

• test(0) 读第 0 位，是 1。
• any() 问“有没有 1”，有；none() 问“是不是全 0”，不是；all() 问“是不是全 1”，不是。三者都是 bool，打印成 0/1。
• count() 是 1 的个数（2），size() 是位数（8）。
• 不带参数的 set() 把所有位置 1，reset() 把所有位置 0。所以 set() 后 all() 为 1，reset() 后 none() 为 1。

移位会丢弃越界的位

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> b("10000001");

    cout << "左移 1 位：" << (b << 1) << '\n';
    cout << "右移 1 位：" << (b >> 1) << '\n';
    cout << "原值不变：" << b << '\n';
    return 0;
}

输出：

左移 1 位：00000010
右移 1 位：01000000
原值不变：10000001

b 是 10000001：第 7 位和第 0 位是 1。

• 左移 1 位：所有位往高位方向移动一格，第 7 位的 1 移出宽度之外被丢弃，原来的第 0 位来到第 1 位，结果 00000010。
• 右移 1 位：所有位往低位方向移动一格，第 0 位的 1 被丢弃，原来的第 7 位来到第 6 位，结果 01000000。
• 移位不会改变原来那个 bitset，b 仍是 10000001。要保存结果得用另一个变量接住，或写 b <<= 1。

什么时候选它、哪里容易错

位数固定，不能改。 bitset<8> 永远是 8 位，不能加一位、减一位。位数需要随运行情况变化时，用 vector<bool> 或别的结构。

字符串方向和位下标是反的。 字符串从左到右是“高位到低位”，位下标从右往左是“0 到 N-1”。看到 "00000101" 时先数右边：最后一位是第 0 位。

operator[] 不检查边界，test 会检查。 b[i] 像数组下标一样，i 超出 [0, N) 是未定义行为：

// 错误示例：位下标 8 超出了 bitset<8> 的范围，operator[] 不检查边界
#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> b("00000101");
    b[8] = 1;          // 越界，未定义行为
    return 0;
}

这段能编译，但 b[8] 越界，结果不确定，本页不给它写运行结果。相比之下，test(i) 在 i 越界时会抛出 out_of_range 异常。下面用 try { … } catch (…) { … } 把它接住：这段代码一旦抛出异常，就跳到 catch 里继续执行，而不是让程序当场结束（异常是进阶话题，这里只要看懂“越界会被发现”这一点）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> b("00000101");

    try {
        b.test(8);          // 下标 8 越界，test 会抛异常
        cout << "没有异常" << '\n';
    } catch (const out_of_range&) {
        cout << "越界时抛出了 out_of_range 异常" << '\n';
    }
    return 0;
}

输出：

越界时抛出了 out_of_range 异常

所以：要安全读一位，用 test 并保证下标合法；要改写一位，用 set(i, v) 或 reset(i)，并自己保证下标在范围内。

移位会丢位。 左移、右移时，移出固定宽度的位直接消失，不会“存到别处”。位数固定意味着 bitset<8>("10000001") << 1 的结果是 00000010，最高位那个 1 没了。

按位运算要求位数相同。 a & b 里的两个 bitset 必须位数一致（模板参数相同），否则编译不过。

to_ulong / to_ullong 有位数限制（选读）。 它们把整个 bitset 转成一个整数：

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> b("00000101");

    cout << "to_ulong()：" << b.to_ulong() << '\n';
    cout << "to_ullong()：" << b.to_ullong() << '\n';
    return 0;
}

输出：

to_ulong()：5
to_ullong()：5

to_ulong 要求位数不超过 unsigned long 的宽度，to_ullong 要求不超过 unsigned long long 的宽度；超出可表示范围时它们会抛出 overflow_error，所以位数多的时候不要随便调用。日常按位操作不必用到它们。

选读。 bitset 内部把若干位打包进机器字，所以 count、any 这类整体操作很快。具体怎么打包是实现细节，不影响你怎么使用。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

bitset<8> b("00001111");
b.flip(0);
b.set(4);
cout << b << ' ' << b.count() << '\n';

第 2 题：修改代码

下面这段片段从 "00000101" 出发。请补上“把最高位（第 7 位）置 1”的操作，让输出变成 10000101 3：

bitset<8> b("00000101");
// 在这里补一行：把第 7 位置 1
cout << b << ' ' << b.count() << '\n';

验证条件：先说出补完之后一共几个 1，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> b("00001111");
    b.flip(0);
    b.set(4);
    cout << b << ' ' << b.count() << '\n';
    return 0;
}

00011110 4

#include <bits/stdc++.h>
using namespace std;

int main() {
    bitset<8> b("00000101");
    b.set(7);
    cout << b << ' ' << b.count() << '\n';
    return 0;
}

10000101 3

立即练习

这道题要用到本页的位下标、移位和整数转换。做完后请说明：交换高低 16 位时，为什么“往左移 16 位”和“往右移 16 位”就能把两半调换位置？