温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

位图BitMap

发布时间:2020-06-13 10:31:19 来源:网络 阅读:370 作者:Sekai_Z 栏目:编程语言

引子:

    给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;
	 
};




未完待续

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI