摘要：
位图中的值可以是计数和标识（如图所示）。因为无符号数据的最大范围约为40亿，40*10^8/1024*1024*8=476，所以只需要512M的内存空间，每个位代表一个无符号数据。
1.位图的介绍：
位图就是通过将数组下标与应用中的一些值关联，数组中该下标所指定的位置上的元素可以用来标识应用中值的情况（是否存在 or 数目 or 。。。）。
位图中的值可以是计数、标识（如图）。
2.位图的应用：
1.给40亿个不重复的unsigned int的整数，没有排过序，然后再给一个数，如果快速判断这个数是否在那40亿个数当中。
因为unsigned int数据的最大范围在在40亿左右，40*10^8/1024*1024*8=476，因此只需申请512M的内存空间，每个bit位表示一个unsigned int。读入40亿个数，并设置相应的bit位为1.然后读取要查询的数，查看该bit是否为1，是1则存在，否则不存在。
2.给40亿个unsigned int的整数，如何判断这40亿个数中哪些数重复？
同理，可以申请512M的内存空间，然后读取40亿个整数，并且将相应的bit位置1。如果是第一次读取某个数据，则在将该bit位置1之前，此bit位必定是0；如果是第二次读取该数据，则可根据相应的bit位是否为1判断该数据是否重复。
/*位图代码的自己的实现*/
class BitMap { public: BitMap() :_size(0) {} BitMap(size_t size) :_size(0) { _arrays.resize((size >> 5) + 1); } bool Set(size_t num) { size_t index = num >> 5; size_t n = num % 32; if (_arrays[index] & (1 << n)) { return false; } _arrays[index] |= (1 << n); ++_size; return true; } bool ReSet(size_t num) { size_t index = num >> 5; size_t n = num % 32; if (_arrays[index] & (1 << n)) { _arrays[index] &= (~(1 << n)); --_size; return true; } else { return false; } } bool Test(size_t num) { size_t index = num >> 5; size_t n = num % 32; return _arrays[index] & (1 << n); } void Clear() { _arrays.assign(_arrays.size(), 0); } public: vector<size_t> _arrays; size_t _size; };
如果有什么意见或建议的请不吝赐教 ^_^