位图BitMap-创新互联
引子:
创新互联主要从事网站建设、网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务平远,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792给40亿个不重复的无符号整数,没排过序,给一个无符号整数,如何判断这个数是否在这40亿个数中。
分析:1 字节=8位
1 KB =1024字节=2^10字节
1 MB =1024KB
1 GB =1024MB
40亿个数,40亿可以约看为2^32,即需要将近4G的空间存储,,如果内存够的话,40亿个整数使用位图存储需要500M的空间
位图即每一个位存储,如果这个数存在,则先找到这个字节大小,再将字节的这个位置1
templateclass 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许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
分享题目:位图BitMap-创新互联
网页链接:http://scyanting.com/article/coooij.html