位图bit地图

位图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;}

?

???????