bitset位图

一、核心特性

1. 编译期固定大小：大小必须是编译期常量（模板参数），无法动态扩容 / 缩容
2. 极致内存效率：每个元素仅占1 位（比bool数组省 8 倍内存，bool数组每个元素至少 1 字节）
3. 原生位运算支持：重载了所有位运算符（&、|、^、~、<<、>>），可批量操作位
4. 值语义：支持拷贝、赋值、比较，无引用语义
5. 无动态内存分配：所有内存都在栈上分配，性能极高

二、定义与初始化

头文件：#include <bitset>语法：std::bitset<N> bs;其中N是位的总数，必须是编译期常量

常用初始化方式

#include <bitset> #include <string> using namespace std; int main() { // 1. 默认初始化：所有位为0 bitset<8> b1; // 00000000 // 2. 用无符号整数初始化（低位对齐） bitset<8> b2(0b1011); // 00001011 bitset<8> b3(11); // 同上，11的二进制是1011 // 3. 用字符串初始化（字符串最右侧对应bitset第0位） bitset<8> b4("1011"); // 00001011 bitset<8> b5("11001011"); // 11001011 // 4. 拷贝初始化 bitset<8> b6(b2); // 00001011 return 0; }

⚠️关键注意点：

• 字符串初始化时，字符串的最右侧字符对应 bitset 的第 0 位（最低位）
• 字符串只能包含'0'和'1'，否则会抛出std::invalid_argument异常
• 若整数 / 字符串的位数小于N，高位自动补 0；若大于N，整数取低位，字符串取右侧N位

三、元素访问与操作

1. 单个位访问

bitset<8> b(0b1011); bool bit0 = b[0]; // true（第0位是1） bool bit3 = b.test(3); // true（第3位是1） b[1] = 0; // 第1位置0 → 00001001 b[2].flip(); // 第2位取反 → 00001101

2. 批量位操作

bitset<8> b; b.set(); // 11111111 b.reset(3); // 11110111 b.flip(); // 00001000

3. 状态查询

bitset<8> b(0b1011); size_t cnt = b.count(); // 3 bool has_one = b.any(); // true bool all_zero = b.none(); // false bool all_one = b.all(); // false

四、位运算支持

std::bitset重载了所有位运算符，仅支持相同大小的 bitset 之间运算

bitset<4> a(0b1010); bitset<4> b(0b1100); bitset<4> c = a & b; // 1000 bitset<4> d = a | b; // 1110 bitset<4> e = a ^ b; // 0110 bitset<4> f = ~a; // 0101 bitset<4> g = a << 1; // 0100 bitset<4> h = a >> 1; // 0101

五、类型转换

bitset<8> b(0b1011); unsigned long ul = b.to_ulong(); // 11 string s = b.to_string(); // "00001011"

六、底层实现原理

1. 存储结构

std::bitset内部通过整数数组存储位，通常以unsigned long long（64 位）为基本存储单元。 对于N位的 bitset，需要的存储单元数为：(N + 63) / 64（向上取整）。

例如：

• bitset<100>：需要 2 个unsigned long long（共 128 位），剩余 28 位未使用
• bitset<64>：需要 1 个unsigned long long

2. 位索引映射

• 第 0 位（最低位）对应第一个存储单元的最低位
• 第 64 位对应第二个存储单元的最低位
• 以此类推

这种设计的优势：CPU 的位运算指令天然支持 64 位批量操作，使得count()、&、|等操作可以一次处理 64 位，性能极高。

3. 代理类reference

bitset::operator[]返回的不是bool&，而是一个内部代理类reference。原因：C++ 不允许直接返回一个位的引用（内存最小寻址单位是字节）。

代理类reference重载了以下操作，使得它可以像bool&一样使用：

• operator bool() const：隐式转换为 bool
• operator=(bool) const：赋值
• flip() const：取反

这是面试中非常高频的考点。

七、优缺点对比

优点

• 极致的内存效率：1 位存储一个布尔值
• 极快的位运算：利用 CPU 原生指令，批量处理 64 位
• 无动态内存分配：栈上分配，性能稳定
• 类型安全：编译期检查大小，避免越界

缺点

• 大小必须是编译期常量，无法动态调整
• 无迭代器，无法使用大部分 STL 算法
• 超过 64 位时无法转换为整数类型
• 作为函数参数时必须用模板，增加代码复杂度

八、与类似结构的对比

九、常见面试考点

1. bitset 和 vector<bool>的区别？

   • 大小：bitset 编译期固定，vector<bool>动态可变
   • 性能：bitset 无动态内存分配，位运算更快
   • 功能：bitset 原生支持位运算，vector<bool>不支持

2. 为什么 bitset 的 operator [] 返回代理类而不是 bool&？

   • 因为内存最小寻址单位是字节，无法直接返回一个位的引用
   • 代理类通过重载运算符模拟了 bool & 的行为

3. bitset 的 count () 函数为什么这么快？

   • 现代 CPU 支持popcnt指令，可以一次统计一个 64 位整数中 1 的个数
   • bitset 的 count () 会利用该指令，批量处理每个存储单元

4. 如何实现动态大小的位图？

   • 可以用vector<unsigned long long>作为底层存储
   • 手动实现位的访问、修改和位运算
   • 也可以使用 boost 库的dynamic_bitset