位图的使用

1、位图介绍

如整型int占32位，则一个int可以表示 0~ 31 这些数，第0位表示0是否出现过，第1位表示1是否出现过，以此类推…

2、位图的功能

如果数字的最大范围是确定的，就可以使用位图来收集数字并判断是否存在

3、位图的好处

极大地压缩空间

4、位图的实现

以 long 存储收集数字为例：

/*************************************************************************> File Name: 023.位图.cpp> Author: Maureen > Mail: Maureen@qq.com > Created Time: 三  4/27 17:20:56 2022************************************************************************/#include 
#include 
#include 
using namespace std;class BitMap {
private:long *bits;public:BitMap(int max) {//（max+64) >> 6  等同于 （max+64) >> 64，为了表示该范围，确定数组中的数的个数//比如要表示0~64，则需要的long类型的个数为 (64 + 64)/64 = 2 个bits = new long[(max + 64) >> 6]; }void add(int num) {//比如将170放到该数组中，则它应该定位在 170/64 这个位置的整数//而这个170对应于这个整数的第几位呢？ 170 % 64 （从右往左数）//一定要写1L，才表示64位，单独的1默认表示32位// num >> 64  -> 定位到是哪个整数// num % 64 等同于 num & 63，  bits[num >> 6] |= (1L << (num & 63)); //将对应整数的对应位标为1}   void del(int num) {//位图中删除某个数，//比如1011011011（从右往左数）第3位想要将其有1变为0，于是就 & 1111110111，而这个数就是下式的右侧bits[num >> 6] &= ~(1L << (num & 63)); //将num所在位变为0}bool contains(int num) {//位图中查找某个数//判断某位是否为1，只需要该位为1，其他位为0，这个数与位图进行与操作，结果如果是0就表示不存在，否则存在return (bits[num >> 6] & (1L << (num & 63))) != 0;}
};int main(){srand(time(0));int testTime = 10000000;int max = 10000;BitMap *bitmap = new BitMap(max);unordered_set<int> s;cout << "Test begin:" << endl;for (int i = 0; i < testTime; i++) {int num = rand() % (max + 1);double decide = rand() % 101 / (double)101;if (decide < 0.333) {bitmap->add(num);s.insert(num);} else if (decide < 0.666) {bitmap->del(num);s.erase(num);} else {if (bitmap->contains(num) != (s.count(num) != 0)) {cout << "Oops!" << endl;break;}}}for (int num = 0; num <= max; num++) {if (bitmap->contains(num) != (s.count(num) != 0)) {cout << "Oops!" << endl;}}cout << "Test end!" << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！