引子：

给40亿个不重复的无符号整数，没排过序，给一个无符号整数，如何判断这个数是否在这40亿个数中。

分析：1 字节=8位

1 KB =1024字节=2^10字节

1 MB =1024KB

1 GB =1024MB

40亿个数，40亿可以约看为2^32，即需要将近4G的空间存储，，如果内存够的话，40亿个整数使用位图存储需要500M的空间


位图即每一个位存储，如果这个数存在，则先找到这个字节大小，再将字节的这个位置1

template<classT>classBitMap{public:BitMap(size_tn):_size(0){_a.resize((n>>5)+1);//map存储数据时是按位存储，n>>5即n/32}voidset(size_tx)//置位{size_tindex=x>>5;//即x/32size_tnum=x%32;if((_a[index]&(1<<num))==0)//先判断当前位是否已被置1，若还没被置1，则_size++且置1{_size++;_a[index]|=(1<<num);}}voidReset(size_tx)//取消置位{size_tindex=x>>5;size_tnum=x%32;if((_a[index]&(1<<num))!=0)//若当前位不为0则_size--后置0{_size--;_a[index]&=~(1<<num);}}inttest(size_tx){size_tindex=x>>5;size_tnum=x%32;return_a[index]&(1<<num);}private:vector<T>_a;size_t_size;};




未完待续