位图bitmap

        bitmap是一种广泛使用的数据结构，主要用在数据压缩，索引等方面，它最小单位为位，即01结构。通常情况下逻辑状态为是非二值状态时，bitmap比较常用。

        如：腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

        显然可以发现，需要判断给出的整数是否存在，是一个二值逻辑，可以用bitmap来解决。我们可以用bitmap来建立一个hashmap，消耗O(N)的预处理时间，去实现O(1)的查询。我们发现40亿刚好可以用unsigned来表示.

        如何构造hash函数，其实很简单，1）确定hashmap的容量，由于整数类型为unsigned int，容量unsigned MAXI=(1<<32)-1;接着建立数组int a[MAXI/32+1]. 2）对于每个整数i，i/32对应数组a中的位置，i%32对于a[i/32]这个32位二进制的位置。

举个例子：对于号码 89256,由于89256 mod 32=2789…8,这样我们应该置a[2789]中32位字符串的第8位(从低位数起)为1.

#include<iostream>
using namespace std;
#define WORD 32   
#define SHIFT 5 ////移动5个位,左移则相当于乘以32,右移相当于除以32取整   
#define MASK 0x1F //16进制下的31   
#define N 10000000   
int bitmap[1+N/WORD];  
/* 
 * 置位函数——用"|"操作符,i&MASK相当于mod操作 
 * m mod n 运算，当n = 2的X次幂的时候,m mod n = m&(n-1) 
 */  
void set(int i) 
{  
    bitmap[i>>SHIFT]|=(1<<(i&MASK));  
}  
/* 清除位操作，用&~操作符 */  
void clear(int i) 
{  
    bitmap[i>>SHIFT]&=~(1<<(i & MASK));  
}  
/* 测试位操作用&操作符 */  
int test(int i)
{  
    return bitmap[i>>SHIFT]&(1<<(i&MASK));  
}  

int main()
{
	//unsigned i;
	//i=(1<<32)-1;
	//cout<<i<<endl;
	return 0;	
}