位图BitMap-创新互联

引子：

    给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 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_a;
	size_t _size;
	 
};

未完待续

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。