C STL bitset 和位图详解文章目录C STL bitset 和位图详解bitset 是从位图问题引出来的用一个比特位表示一个数是否存在位图的概念位图的应用bitset 的基本认识bitset 的定义方式bitset 常用成员函数bitset 运算符的使用bitset 适合做什么bitset 模拟实现的接口构造函数set、reset、flip、testsize 和 countany、none、all打印函数模拟实现完整代码测试模拟实现再看 40 亿整数问题位图的优缺点总结bitset 是从位图问题引出来的先看一个经典问题给 40 亿个不重复的无符号整数数据没有排序现在再给一个无符号整数要求快速判断这个数是否在这 40 亿个数里面第一反应可能有两种把所有数据排序然后用二分查找把所有数据放进 unordered_set然后用 find 查找从时间复杂度看这两种思路都能说得通排序加二分建表阶段大概是 O(NlogN)查找阶段是 O(logN)unordered_set 建表平均 O(N)查找平均接近 O(1)但这个题真正麻烦的不在时间而是在空间一个无符号整数通常占 4 字节40 亿个整数大概要占 160 亿字节也就是 16GB 左右如果再考虑容器本身的额外开销unordered_set 需要的空间只会更夸张所以这类题不能只盯着查找速度还要先问一句数据能不能放得下用一个比特位表示一个数是否存在这个问题里我们只关心一个数在不在集合中也就是说每个数只有两种状态存在不存在既然只有两种状态其实一个比特位就够表示了比特位为 1表示这个数出现过比特位为 0表示这个数没有出现过无符号整数的取值范围一共有 2^32 种可能如果给每个可能的无符号整数准备一个比特位就需要 2^32 个比特位换算一下2^32 bit 2^29 byte 512MB原来直接存 40 亿个整数需要 16GB 左右现在只需要 512MB 左右这就是位图的核心价值用很小的空间记录大量数据的存在状态位图的概念位图就是用每一个二进制位来存放某种状态它特别适合这类场景数据量很大数据范围相对明确只关心存在或者不存在通常不需要记录重复次数比如要记录整数 x 是否出现过就可以把第 x 个比特位设置成 1查找 x 是否存在时再去检查第 x 个比特位是不是 1这个过程本质上不需要比较也不需要哈希冲突处理定位到对应的位就行不过位图也有明显限制它适合整数范围比较集中的场景如果数据是一些很分散的超大整数或者字符串直接拿位图就不太合适如果要处理字符串一般要先经过哈希映射但这样又会带来哈希冲突问题位图的应用位图的典型应用不少快速判断某个数据是否在集合中对整数数据做去重对一定范围内的整数做排序求两个集合的交集和并集操作系统中标记磁盘块是否被占用内核中记录信号屏蔽字和未决信号集位图做排序的思路也很直观先把出现过的整数对应的位设置成 1然后从低位到高位扫描整个位图遇到值为 1 的位就输出这个位对应的整数因为扫描顺序本身就是从小到大所以输出结果天然有序但这种方式只适合不需要保留重复次数的整数排序如果数据里有重复值而你又要保留重复次数那普通位图就不够了这时可以考虑计数数组或者在位图基础上做扩展bitset 的基本认识C 标准库里提供了 bitset它可以理解成一个固定大小的位图使用 bitset 需要包含头文件#includebitsetbitset 的大小在编译期确定比如 bitset16 表示它有 16 个比特位这 16 位的下标范围是 0 到 15下标 0 表示最低位下标 15 表示最高位这点在看输出时很容易弄混比如设置第 0 位打印出来时通常会出现在最右边bitset 的定义方式方式一构造一个指定大小的 bitset所有位默认都是 0#includeiostream#includebitsetusingnamespacestd;intmain(){bitset16bs1;coutbs1endl;// 0000000000000000return0;}方式二通过整数初始化#includeiostream#includebitsetusingnamespacestd;intmain(){bitset16bs2(0xfa5);coutbs2endl;// 0000111110100101return0;}0xfa5 的二进制低 16 位会被放进 bitset 里如果整数的二进制位数少于 bitset 的长度高位会自动补 0方式三通过 0 和 1 组成的字符串初始化#includeiostream#includebitset#includestringusingnamespacestd;intmain(){bitset16bs3(string(10111001));coutbs3endl;// 0000000010111001return0;}字符串右边的字符会对应 bitset 的低位所以字符串 “10111001” 初始化到 bitset16 里打印时前面会补 0bitset 常用成员函数bitset 常用成员函数如下成员函数功能set设置指定位或所有位reset清空指定位或所有位flip反转指定位或所有位test获取指定位的状态count获取被设置为 1 的位数size获取 bitset 能容纳的位数any判断是否至少有一个位为 1none判断是否所有位都是 0all判断是否所有位都是 1to_string转成由 0 和 1 组成的字符串to_ulong转成 unsigned longto_ullong转成 unsigned long longset、reset、flip 都有两个常见用法一种是操作指定位置另一种是不传下标直接操作所有位#includeiostream#includebitsetusingnamespacestd;intmain(){bitset8bs;// 把第 1 位和第 3 位置成 1bs.set(1);bs.set(3);coutbsendl;// 00001010// 清掉第 1 位bs.reset(1);coutbsendl;// 00001000// 把第 3 位从 1 翻成 0bs.flip(3);coutbsendl;// 00000000// 不传下标时表示操作全部位bs.set();coutbsendl;// 11111111bs.reset();coutbsendl;// 00000000bs.flip();coutbsendl;// 11111111return0;}test 用来判断某一位是不是 1count 用来统计有多少位是 1#includeiostream#includebitsetusingnamespacestd;intmain(){bitset8bs(string(10110010));// test 检查某一位是否为 1coutbs.test(1)endl;// 1coutbs.test(2)endl;// 0// count 统计 1 的个数size 返回总位数coutbs.count()endl;// 4coutbs.size()endl;// 8// any/none/all 用来做整体状态判断coutbs.any()endl;// 1coutbs.none()endl;// 0coutbs.all()endl;// 0return0;}这里的 test(1) 看的是从右往左数的第 1 位因为 bitset 的下标 0 是最低位bitset 运算符的使用bitset 支持不少位运算相关的运算符运算符功能[]访问或修改某一位按位与|按位或^按位异或~按位取反按位与后赋值|按位或后赋值^按位异或后赋值左移右移左移后赋值右移后赋值判断两个 bitset 是否相等!判断两个 bitset 是否不相等直接用 [] 可以访问某一位#includeiostream#includebitsetusingnamespacestd;intmain(){bitset8bs;// 下标 0 对应最低位所以会显示在最右边bs[0]1;bs[3]1;coutbsendl;// 00001001coutbs[3]endl;// 1return0;}位运算可以用来做集合操作比如一个 bitset 表示一个集合某一位为 1 表示这个元素存在两个 bitset 按位与可以得到交集两个 bitset 按位或可以得到并集#includeiostream#includebitsetusingnamespacestd;intmain(){bitset8s1(string(00101101));bitset8s2(string(00011110));// 可以把 bitset 当成位集合来做交并差相关操作cout(s1s2)endl;// 00001100cout(s1|s2)endl;// 00111111cout(s1^s2)endl;// 00110011cout(~s1)endl;// 11010010return0;}左移和右移也比较常见#includeiostream#includebitsetusingnamespacestd;intmain(){bitset8bs(string(00001111));// 移出去的位会丢掉左边或右边空出来的位置补 0cout(bs2)endl;// 00111100cout(bs2)endl;// 00000011bs1;coutbsendl;// 00011110return0;}移出去的位会丢掉空出来的位置补 0bitset 适合做什么bitset 最适合处理固定范围内的布尔状态比如标记某个编号是否出现过记录一组开关状态做集合的交并差相关操作保存一些标志位在数据范围固定时做快速去重如果位数在编译期就确定用 bitset 很方便如果位数需要运行时才能确定标准库的 bitset 就不太合适这时可以自己用 vector 做动态位图后面的模拟实现就是这个思路bitset 模拟实现的接口为了避免和标准库 bitset 冲突模拟实现时放到自己的命名空间里接口可以先按下面这一版来设计namespacecl{templatesize_t Nclassbitset{public:bitset();voidset(size_t pos);voidreset(size_t pos);voidflip(size_t pos);booltest(size_t pos)const;size_tsize()const;size_tcount()const;boolany()const;boolnone()const;boolall()const;voidPrint()const;private:vectorunsignedint_bits;};}这里的 N 是非类型模板参数它表示位图能表示多少个比特位底层不是真的开 N 个 bool而是用整数数组来压缩存储一个 unsigned int 通常有 32 个比特位所以 N 个比特位需要的整数个数大概是(N 31) / 32有些写法会用 N / 32 1 来算这样也能覆盖大多数场景比如 N 为 40 时需要 40 / 32 1也就是 2 个整数不过如果 N 正好是 32 的倍数N / 32 1 会多开一个整数所以这里实现时用 (N 31) / 32更贴近实际需要构造函数构造函数要做的事很简单根据 N 算出需要多少个整数然后全部初始化为 0bitset(){_bits.resize((N31)/32,0);}如果 N 是 100那么需要 4 个 unsigned int因为 3 个只能提供 96 个比特位多出来的那些不用的高位平时不参与逻辑判断set、reset、flip、test要操作第 pos 位先要算出它在第几个整数里再算出它是这个整数里的第几个比特位假设一个整数有 32 位i pos / 32 j pos % 32i 表示第几个整数j 表示这个整数里的第几个比特位设置第 pos 位为 1_bits[i]|(1uj);清空第 pos 位_bits[i]~(1uj);反转第 pos 位_bits[i]^(1uj);测试第 pos 位return(_bits[i](1uj))!0;写成成员函数就是voidset(size_t pos){assert(posN);size_t ipos/32;size_t jpos%32;_bits[i]|(1uj);}voidreset(size_t pos){assert(posN);size_t ipos/32;size_t jpos%32;_bits[i]~(1uj);}voidflip(size_t pos){assert(posN);size_t ipos/32;size_t jpos%32;_bits[i]^(1uj);}booltest(size_t pos)const{assert(posN);size_t ipos/32;size_t jpos%32;return(_bits[i](1uj))!0;}这里用了 assert 做越界检查标准库 bitset 的 test 越界会抛异常operator[] 不做边界检查我们这里是模拟实现用 assert 更简单size 和 countsize 返回位图能容纳的位数也就是模板参数 Nsize_tsize()const{returnN;}count 用来统计有多少位是 1最直接的办法是从 0 到 N - 1一个一个调用 testsize_tcount()const{size_t ret0;for(size_t i0;iN;i){if(test(i)){ret;}}returnret;}这种写法简单清楚适合学习实现如果想做得更快可以按整数块统计每个 unsigned int 里有多少个 1不过模拟 bitset 时先把逻辑写明白更重要any、none、allany 判断是否至少有一个位是 1只要某个整数块不为 0就说明有位被设置了boolany()const{for(autovalue:_bits){if(value!0){returntrue;}}returnfalse;}none 判断是否所有位都是 0它刚好可以复用 anyboolnone()const{return!any();}all 判断是否所有有效位都是 1最简单的写法是看 count 是否等于 Nboolall()const{returncount()N;}注意最后一个整数里可能有一些多余位比如 bitset40 底层用了两个 unsigned int实际有 64 个比特位空间但只有前 40 位有效所以 all 不能直接判断每个整数是不是全 1用 count() N 就能避开这个问题打印函数打印时通常从高位往低位打印这样结果和标准库 bitset 输出习惯一致voidPrint()const{for(size_t iN;i0;--i){couttest(i-1);}coutendl;}比如设置第 0 位和第 3 位后打印结果是00001001第 0 位在最右边这个习惯和整数二进制展示方式一致模拟实现完整代码下面给一份完整代码这个版本保留前面设计的接口又补完整了成员函数实现#includeiostream#includevector#includecassertusingnamespacestd;namespacecl{templatesize_t Nclassbitset{public:bitset(){// N 个比特位按 32 位一个整型来存_bits.resize((N31)/32,0);}voidset(size_t pos){assert(posN);// i 表示落在哪个整型里j 表示这个整型中的第几位size_t ipos/32;size_t jpos%32;_bits[i]|(1uj);}voidreset(size_t pos){assert(posN);size_t ipos/32;size_t jpos%32;// 对目标位取反掩码再按位与清零_bits[i]~(1uj);}voidflip(size_t pos){assert(posN);size_t ipos/32;size_t jpos%32;// 异或 1 可以把这一位翻转_bits[i]^(1uj);}booltest(size_t pos)const{assert(posN);size_t ipos/32;size_t jpos%32;// 只要目标位与出来不是 0就说明这一位是 1return(_bits[i](1uj))!0;}size_tsize()const{returnN;}size_tcount()const{size_t ret0;// 这里直接按有效位逐个统计逻辑最直观for(size_t i0;iN;i){if(test(i)){ret;}}returnret;}boolany()const{for(autovalue:_bits){// 任意一个整型块非 0就说明至少有一位被设置if(value!0){returntrue;}}returnfalse;}boolnone()const{return!any();}boolall()const{// 只比较有效位避免最后一个整型里的无效位干扰判断returncount()N;}voidPrint()const{// 从高位往低位打印输出风格和标准库 bitset 一致for(size_t iN;i0;--i){couttest(i-1);}coutendl;}private:vectorunsignedint_bits;};}测试模拟实现写一个简单测试看看 set、reset、flip、test、count、any、none、all 是否正常intmain(){cl::bitset16bs;// 初始时所有位都是 0bs.Print();// 0000000000000000// 把几个位置成 1观察打印结果是否符合预期bs.set(0);bs.set(3);bs.set(7);bs.Print();// 0000000010001001// 读接口测试coutbs.test(3)endl;// 1coutbs.test(4)endl;// 0coutbs.count()endl;// 3coutbs.size()endl;// 16// 整体状态测试coutbs.any()endl;// 1coutbs.none()endl;// 0coutbs.all()endl;// 0// 翻转和清零测试bs.flip(3);bs.Print();// 0000000010000001bs.reset(7);bs.Print();// 0000000000000001return0;}如果要支持 set 全部位、reset 全部位、flip 全部位也可以继续加重载函数voidset(){for(size_t i0;iN;i){set(i);}}voidreset(){for(autovalue:_bits){value0;}}voidflip(){for(size_t i0;iN;i){flip(i);}}这里 set 和 flip 选择按有效位逐个处理因为最后一个整数里可能有无效位如果直接把每个 unsigned int 都设置成全 1会把那些无效位也设置掉虽然 Print、count、all 都只看有效位时问题不大但学习实现时最好把有效位和无效位分清楚再看 40 亿整数问题现在回到开头的问题如果要判断某个无符号整数 x 是否出现过可以准备一个足够大的位图读取到数字 x 时把第 x 位设置成 1查询 x 是否存在时检查第 x 位是不是 1如果用标准库 bitset理论上可以这样表达bitset4294967296bs;但这个写法在实际编译环境里不一定合适原因是 bitset 的大小是编译期常量这么大的对象也不适合随便放在栈上真实工程里更常用动态位图也就是用 vector 或 vector 这种方式按需开空间标准库还有 vector 这种特殊化容器它也会做位压缩但 vector 的接口和普通 vector 不完全一样用的时候要知道它不是普通 bool 数组位图的优缺点位图的优点很明显空间压缩效果非常好判断存在与否很快对固定整数范围非常友好可以用位运算快速做集合交并缺点也要记住不适合直接处理范围特别离散的数据只能表示存在或不存在不能表示出现次数如果最大值很大但实际数据很少空间可能会浪费对非整数 key 通常需要哈希转换可能引入冲突所以位图不是万能结构它适合的是那种范围明确、状态简单、数据量很大的问题总结bitset 可以看成 C 标准库提供的固定大小位图它用每一个比特位表示一个状态所以特别适合保存大量布尔状态位图最大的价值是省空间40 亿个无符号整数如果直接存大概需要 16GB如果只记录出现状态用 2^32 个比特位就够大概是 512MB使用 bitset 时要记住几个点bitset 的大小在编译期确定下标 0 表示最低位set、reset、flip 分别用于置位、清位、反转test 用来检查某一位状态count、any、none、all 用来做整体判断、|、^、~ 可以做位集合运算模拟实现时核心就是三步用整数数组保存所有比特位通过 pos / 32 找到整数下标通过 pos % 32 找到整数中的比特位把这套映射关系想清楚以后set、reset、flip、test 这些接口就很好写了