数学的集合这个概念，可以用 C 的布尔数组实现。然而，使用 bool 类型，导致每一个元素都会占用一个字节。
实际上，每一个字节理论上能存 8 个元素的状态，可以使用 char 或 int 数组来模拟。
而 C++ STL 自带了一种数据结构，bitset，就不用自己手写啦。
声明
1 |
|
定义和初始化
1 | bitset<32> b; //32位，全为0。 |
给出的长度值必须是常量表达式。
位集合的位置编号从 0 开始，因此，bs 的位序是从 0 到 31。以0位开始的位串是低阶位（low-order bit），以31位结束的位串是高阶位(high-order bit)。
简单的来说就是，bitset 和数组一样，从 string 的角度看，string 的顺序和 bitset 顺序是相反的（string 的最后一位被赋给了 bitset 第一位）；从 unsigned long 的角度看，从左往右是从低位到高位。
bitset 有以下构造函数：
1 | bitset<n> b; //b有 n 位，每位都为 0 |
貌似不是很好懂，但只要记住以下形式等价即可：
bitset<8> b("11000");bitset<8> b(24); //24(10) == 00011000(2)bitset<8> b; b[3] = b[4] = 1;
并且记住“过多则忽略高位，过少则置高位为 0” 的原则。
访问 bitset 的位
使用 b[] 即可。
bitset 的一堆函数
| 函数名 | 函数作用 |
|---|---|
bool b.all() |
检查 b 中是否全部位被设为 1 |
bool b.any() |
检查 b 中是否任一位被设为 1 |
bool b.none() |
检查 b 中是否无位被设为 1 |
size_t b.count() |
返回设为 1 的位数 |
size_t b.size() |
返回 bitset 的大小，即 bitset 定义参数中的 n |
bool b.test(pos) |
类似 operator[]，但是进行越界检查，若越界则抛出 std::out_of_range |
b.set() |
设置所有位为 1 |
b.set(size_t pos, bool value = true) |
类似使用 b[pos] = value 赋值，但是进行越界检查，同上 |
b.reset() |
设置所有位为 0 |
b.reset(size_t pos) |
类似 于b[pos] = 0 赋值为 0，但是进行越界检查，同上 |
b.flip() |
类似于 ~b，但是在原位，不进行 Copy Construction |
b[0].flip() |
等价于 b[0] = ~b[0] |
b.flip(size_t pos) |
仅翻转 pos 位（翻转 1 和 0），进行越界检查 |
输出 bitset 的函数
1. to_string(char zero = '0', char one = '1')
1 | template< |
用 zero 表示 0，用 one 表示 1，返回 bitset 的 basic_string （大概是广义的 string？）形式。
默认 to_string() 就是返回 bitset 的 01 串的 string。
2. to_ullong()
unsigned long long bitset::to_ullong()
转换 bitset 的内容为 unsigned long long 整数。
和构造 bitset 一样，bitset 的首位对应数的最低位，而尾位对应最高位。
如果不能用 unsigned long long 表示，则抛出 std::overflow_error。
（有意思的是，只有 bitset 的这两个函数会抛出 std::overflow_error 异常）
3. b.to_ulong()
和上面一样，就是改下数据范围。
为什么介绍这么草率呢？因为 MSVC 的实现是先强转为 unsigned long long 再转为 unsigned long 判越界。貌似也没什么毛病.jpg
1 | _NODISCARD unsigned long to_ulong() const |
题外话：bitset::any(), none(), all(), count() 的实现
bitset::any()，bitset::none()，bitset::all()，bitset::count()，这四个函数都可以通过记录 count，每次修改时记录 count 的变化，来实现 O(1) 的时间复杂度，然而 MSVC 2017 和 GCC 4.7.1 的实现是 O(n) 的。
猜测原因是记录 count 的变化会在修改 bitset 时花费更多的时间，对于不使用这四个函数的用户，这样会使程序变慢。而对于需要 O(1)时间复杂度的用户，手动实现类似功能是很方便的。
但是平时使用的时候需要注意时间复杂度是 O(1) 的。
另外，在 bitset::count() 的实现上，GCC 使用了汇编指令 POPCNT，而 MSVC 使用的是如下的神奇代码：
1 | _NODISCARD size_t count() const noexcept |
其实就是把每个 byte 的 256 种情况对应的 1 的数量打了个表。
Stack Overflow 上有人提到为什么 MSVC 不使用 POPCNT实现，POPCNT 比这样实现更快。
回答是 POPCNT 在部分 CPU 架构上的结果是不可预测的，而 MSVC 更想要跨架构的通用解决方案。
这篇博客的测试中显示， POPCNT 比打表形式快了约 2.7 倍。
