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

一.引子——面试题——海量数据处理(判断某个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。

三.优缺点