引子：
给40亿个不重复的无符号整数，没排过序，给一个无符号整数，如何判断这个数是否在这40亿个数中。
分析：1 字节=8位
1 KB =1024字节=2^10字节
1 MB =1024KB
1 GB =1024MB
40亿个数，40亿可以约看为2^32，即需要将近4G的空间存储，，如果内存够的话，40亿个整数使用位图存储需要500M的空间
位图即每一个位存储，如果这个数存在，则先找到这个字节大小，再将字节的这个位置1
template<class T>
class BitMap
{
public:
BitMap(size_t n)
:_size(0)
{
_a.resize((n>>5)+1);//map存储数据时是按位存储，n>>5即n/32
}
void set(size_t x)//置位
{
size_t index = x >> 5;//即x/32
size_t num = x % 32;
if ((_a[index] & (1 << num)) == 0)//先判断当前位是否已被置1，若还没被置1，则_size++且置1
{
_size++;
_a[index] |= (1 << num);
}
}
void Reset(size_t x)//取消置位
{
size_t index = x >> 5;
size_t num = x % 32;
if ((_a[index] & (1 << num)) != 0)//若当前位不为0则_size--后置0
{
_size--;
_a[index] &= ~(1 << num);
}
}
int test(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
return _a[index] & (1 << num);
}
private:
vector<T>_a;
size_t _size;
};未完待续
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
