最近笔者在做位运算相关的算法题以及学习操作系统信号的三张表时遭遇了许多关于位图的问题。遂作此篇系统地补充一下位图缺失方面的知识点。一.引子——面试题——海量数据处理(判断某个unsigned int在不在40亿个同类数中)但是标记某个数在或不在(1或0)只需要1个bit我们就能从这儿入手玩映射假设40亿个数每个数标记一次不过40亿bit500MB的空间二.实现1.思想由于没法单开1bit的空间我们就复用vectorsize_t每个整型32bit就能映射32个数字那我们如何处理(找到)某个特定的数对应的那一位呢2.实现①.开空间有几个整数就要映射几位这个N就是想要映射的整数的个数(映射的位数)我们用N/32,就能确定vector(_bs)要resize几个整型数据。bit_set() { _bs.resize(N / 32 1);//确认vector里整型数据的个数,1为解决60 / 32 1,而开1个整型绝对不够存60位的情况 }②.置1置1的算法详情参见笔者位运算及其oj题。在置1前我们要先找到X对应位在哪里就要用上面的x / 32确认在哪个整数内用x % 32作为1左移的位数(x % 32是所在的具体哪一位)。void set(size_t x) {//将x对应的位置为1(插入) int i x / 32; int j x % 32; //左移这里左移是低位往高位的移就不用关心大小端的问题。 _bs[i] | (1 j); }③.置0算法思想依旧在位运算及其oj题。void reset(size_t x) {//将第x对应的位置为0(删除) int i x / 32; int j x % 32; _bs[i] (~(1 j)); }④.检测算法思想还是在位运算及其oj题。bool test(size_t x) {//检测 int i x / 32; int j x % 32; return (_bs[i] j) 1; }⑤.传40亿位的方法注意不要用INT_MAX,因为它才21亿多 40亿要用UINT_MAX。三.优缺点