企业官网建设流程全解析

最近笔者在做位运算相关的算法题，以及学习操作系统信号的三张表时，遭遇了许多关于位图的问题。遂作此篇，系统地补充一下位图缺失方面的知识点。

一.引子——面试题——海量数据处理(判断某个unsigned int在不在40亿个同类数中)

但是标记某个数在或不在(1或0)，只需要1个bit，我们就能从这儿入手，玩映射，假设40亿个数每个数标记一次，不过40亿bit，500MB的空间：

二.实现

1.思想

由于没法单开1bit的空间，我们就复用vector<size_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。

三.优缺点