定义
位图法就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。
通常是用来判断某个数据存不存在的。
例如，要判断一千万个人的状态，每个人只有两种状态：男人，女人，可以用0，1表示。那么就可以开一个int数组，一个int有32个位，就可以表示32个人。操作的时候可以使用位操作。 位图实现
unsigned int bit[N];在这个数组里面，可以存储 N * sizeof(int) * 8个数据，但是最大的数只能是N * sizeof(int) * 8 - 1。假如，我们要存储的数据范围为0-15，则我们只需要使得N=1，这样就可以把数据存进去。如下图：
代码实现：
#include<iostream> using namespace std; #include<vector> class BitMap { public: BitMap() { } BitMap(int size) //表示多大的位图 { _table.resize(size/32+1); //如0~40个整数就需要2个int。 } void Set(int data) //将相应的位置1. { //先找到这个数在那个元素中，如39这个数就在下标为1的元素中。 int elemno = data/32; //再找到data所在元素的那个bit位中。 int bitno = data%32; _table[elemno] = _table[elemno] | (1<< bitno); } void ReSet(int data) //将相应的位清0 { //先找到这个数在那个元素中，如39这个数就在下标为1的元素中。 int elemno = data/32; //再找到data所在元素的那个bit位中。 int bitno = data%32; _table[elemno] = _table[elemno] & ( ~(1<< bitno)); } bool Test(int data) //判断data在不在这个位图中 { //先找到这个数在那个元素中，如39这个数就在下标为1的元素中。 int elemno = data/32; //再找到data所在元素的那个bit位中。 int bitno = data%32; return (_table[elemno] & (1<<bitno) ); } private: vector<unsigned int> _table; }; int main() { BitMap bt(100); bt.Set(49); cout << bt.Test(49)<<endl; cout << bt.Test(40)<<endl; cout << "hello..."<<endl; return 0; }位图的缺点： 1.可读性差 2.位图存储的元素个数虽然比一般做法多，但是存储的元素大小受限于存储空间的大小。 3.位图对有符号类型数据的存储，需要 2 位来表示一个有符号元素。这会让位图能存储的元素个数，元素值大小上限减半。
位图的应用： 1）给定25亿个整数，设计算法找到只出现一次的整数 25 00 000 000 *4 / 1000 /1000 /1000 = 10G,把这么多数加载多内存肯定是不可能的，我们使用位图来表示，有三种状态，这个数没有出现过，这个数只是出现一次，这个数多次出现过， 所以我们可以用两个bit来表示，00表示没有出现，01表示出现1次，11表示出现多次。10G/16<1G的内存。 从文件中读取这25亿个整数，如果是第一次存在则从00变成01，如果是多次存在，依旧是10，不变，最终扫描位图，输出比特位为01的整数就行。
2）给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集 10 000 000 000*4/1000/1000/1000 = 40G,不可能加载到内存当中，我们利用hash映射到100份文件中，每份文件平均在0.4G左右，再利用hash表将每份文件的数据存储起来，再判断另外一个相同编号文件的数据是不是在这个hash表中，是的话就是两个文件的交集了，存到文件即可。
