bitset位图

一、核心特性编译期固定大小大小必须是编译期常量模板参数无法动态扩容 / 缩容极致内存效率每个元素仅占1 位比bool数组省 8 倍内存bool数组每个元素至少 1 字节原生位运算支持重载了所有位运算符、|、^、~、、可批量操作位值语义支持拷贝、赋值、比较无引用语义无动态内存分配所有内存都在栈上分配性能极高二、定义与初始化头文件#include bitset语法std::bitsetN bs;其中N是位的总数必须是编译期常量常用初始化方式#include bitset #include string using namespace std; int main() { // 1. 默认初始化所有位为0 bitset8 b1; // 00000000 // 2. 用无符号整数初始化低位对齐 bitset8 b2(0b1011); // 00001011 bitset8 b3(11); // 同上11的二进制是1011 // 3. 用字符串初始化字符串最右侧对应bitset第0位 bitset8 b4(1011); // 00001011 bitset8 b5(11001011); // 11001011 // 4. 拷贝初始化 bitset8 b6(b2); // 00001011 return 0; }⚠️关键注意点字符串初始化时字符串的最右侧字符对应 bitset 的第 0 位最低位字符串只能包含0和1否则会抛出std::invalid_argument异常若整数 / 字符串的位数小于N高位自动补 0若大于N整数取低位字符串取右侧N位三、元素访问与操作1. 单个位访问操作说明边界检查bs[pos]访问第pos位返回代理类reference❌ 越界行为未定义bs.test(pos)检查第pos位是否为 1✅ 越界抛出std::out_of_rangebitset8 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位取反 → 000011012. 批量位操作函数无参数版本带参数版本set()所有位置 1set(pos)第pos位置 1reset()所有位置 0reset(pos)第pos位置 0flip()所有位取反flip(pos)第pos位取反bitset8 b; b.set(); // 11111111 b.reset(3); // 11110111 b.flip(); // 000010003. 状态查询函数说明count()返回值为 1 的位的个数size()返回总位数即模板参数 Nany()是否存在至少一个 1none()是否所有位都是 0all()是否所有位都是 1C11 新增bitset8 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 之间运算运算符说明、按位与、按位或^、^按位异或~按位取反、左移低位补 0、右移高位补 0bitset4 a(0b1010); bitset4 b(0b1100); bitset4 c a b; // 1000 bitset4 d a | b; // 1110 bitset4 e a ^ b; // 0110 bitset4 f ~a; // 0101 bitset4 g a 1; // 0100 bitset4 h a 1; // 0101五、类型转换函数说明注意事项to_ulong()转换为unsigned long若 bitset 大小超过unsigned long位数通常 32 位抛出std::overflow_errorto_ullong()转换为unsigned long longC11若超过 64 位抛出异常to_string()转换为std::string高位在前低位在后bitset8 b(0b1011); unsigned long ul b.to_ulong(); // 11 string s b.to_string(); // 00001011六、底层实现原理1. 存储结构std::bitset内部通过整数数组存储位通常以unsigned long long64 位为基本存储单元。 对于N位的 bitset需要的存储单元数为(N 63) / 64向上取整。例如bitset100需要 2 个unsigned long long共 128 位剩余 28 位未使用bitset64需要 1 个unsigned long long2. 位索引映射第 0 位最低位对应第一个存储单元的最低位第 64 位对应第二个存储单元的最低位以此类推这种设计的优势CPU 的位运算指令天然支持 64 位批量操作使得count()、、|等操作可以一次处理 64 位性能极高。3. 代理类referencebitset::operator[]返回的不是bool而是一个内部代理类reference。原因C 不允许直接返回一个位的引用内存最小寻址单位是字节。代理类reference重载了以下操作使得它可以像bool一样使用operator bool() const隐式转换为 booloperator(bool) const赋值flip() const取反这是面试中非常高频的考点。七、优缺点对比优点极致的内存效率1 位存储一个布尔值极快的位运算利用 CPU 原生指令批量处理 64 位无动态内存分配栈上分配性能稳定类型安全编译期检查大小避免越界缺点大小必须是编译期常量无法动态调整无迭代器无法使用大部分 STL 算法超过 64 位时无法转换为整数类型作为函数参数时必须用模板增加代码复杂度八、与类似结构的对比特性std::bitsetstd::vectorboolbool 数组boost::dynamic_bitset大小编译期固定动态可变固定栈/ 动态堆动态可变内存效率1 位 / 元素1 位 / 元素8 位 / 元素1 位 / 元素迭代器❌✅✅✅位运算支持✅ 原生❌ 需手动实现❌ 需手动实现✅ 原生性能极高中等低高标准库✅✅✅❌ 第三方九、常见面试考点bitset 和 vectorbool的区别大小bitset 编译期固定vectorbool动态可变性能bitset 无动态内存分配位运算更快功能bitset 原生支持位运算vectorbool不支持为什么 bitset 的 operator [] 返回代理类而不是 bool因为内存最小寻址单位是字节无法直接返回一个位的引用代理类通过重载运算符模拟了 bool 的行为bitset 的 count () 函数为什么这么快现代 CPU 支持popcnt指令可以一次统计一个 64 位整数中 1 的个数bitset 的 count () 会利用该指令批量处理每个存储单元如何实现动态大小的位图可以用vectorunsigned long long作为底层存储手动实现位的访问、修改和位运算也可以使用 boost 库的dynamic_bitset