问题场景：对于40亿(4* 10^9)个数据，在计算机中用int存储需要16g内存很占空间(2^30是1g大约是10亿，40亿就是2^32，再就是一个int为4字节，大约就是16 * 2^30，16G)，如果40亿数据直接存储耗费内存，所以按照一个int占四个字节，一个字节八位，如果按照位来存储的话，大约需要16g/32=500M就可以了。
位图的原理: 比如40亿数据用range表示，所以使用int存储的话，只需要 range >> 5个大小空间
找到数据x所在字节位置：x>>5（右移5位，2^5，就是x/32），找到所在第几个字节
找到数据x位的位置：x%32，取模运算，m mod n，也可以使用x& 0x1f
标记数据存在，将数据x相应位置为1： _bitMap[x>>32] |= (1 << (x & 0x1f))
删除数据，将数据x相应的位置为0： _bitMap[x>>32] &= ~(1 << (x & 0x1f))//取反再与操作
查找数据是否存在，直接使用：_bitMap[x>>32] & (1 << (x &0x1f))
代码实现；
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
class BitMap
{
public:
BitMap(size_t range)
{
_bitMap.resize((range > 5) + 1);//例如40亿数据需要开多大空间
}
//标识一个数字在位图中的位置
void setBit(size_t x)
{
size_t index = x >> 5;//一个int是4字节，32位，也就是2^5,所以这里右移动32位找到在_bitMap的下标
size_t num = x % 32;//找到在_bitMap的某个整型位的具体位置
_bitMap[index] |= (1 << num);//该位置置为1，其他位不变
}
void removeBit(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
_bitMap[index] &= ~(1 << num);//该位置置为0，其他位不变
}
//位图元素的查找
bool find(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
return _bitMap[index] & (1 << num);
}
private:
vector<int> _bitMap;
};
void test()
{
size_t a = 4000000000;
cout << "a>>5 = " << (a >> 32) << endl;
}
int main(int argc, char **argv)
{
return 0;
}
原理可以参考：https://blog.csdn.net/weixin_30782331/article/details/97514450
https://blog.csdn.net/sandmm112/article/details/80420141