位图

﹏ヽ暗。殇╰゛Y 2022-06-10 09:26 161阅读 0赞

最近遇到一道题卡空间卡的很厉害，在网上搜了一下，发现了一个叫做位图的数据结构。

位图的原理就是用一个int的32个比特位表示0~31个数是否存在，1表示存在，0表示不存在。

位图优点：

1，速度快。

2，内存空间占用小。

3，能表示大范围数据。

位图的缺点 ：  
       1，可读性差。   
       2，存储元素的个数比一般元素要多，但是存储元素的大小受空间大小的限制。

位图的实现（模板）

class BitMap
    {
    public:
        BitMap(int size = 100)//size表示你需要表示元素的个数
        {
            _map.resize((size >> 5) + 1);//一个int可以表示32个元素，size个元素需要size/32 + 1个int来存储
            //注意+1因为1/32 = 0，但是我们需要一个int
        }
        void set(int num)//将标志位设置为1表示元素存在
        {
            int bite = num >> 5;//相当于/32//找出元素在数组中对应的下标
            int bit = num % 32;//找出元素对应的bit位
            _map[bite] |= (1 << bit);
        }
        void reset(int num)//将已存在元素删除，将对应的标志位置0
        {
            int bite = num >> 5;//相当于/32//找出元素在数组中对应的下标
            int bit = num % 32;//找出元素对应的bit位
            _map[bite] &= ~(1 << bit);
        }
        bool test(int num)
        {
            int bite = num >> 5;//相当于/32//找出元素在数组中对应的下标
            int bit = num % 32;//找出元素对应的bit位
            if (_map[bite] & (1 << bit))
                return true;
            else
                return false;
        }
    private:
        vector<int> _map;
    };

位图的应用

用位图来打1到1e8的素数表

const int MAXN = 10000005;
    const int N = 6000005;
    int prime[N];
    int k;
    BitMap isprime(MAXN);
    
    void getPrime()
    {
    	k = 0;
    	for (int i = 2; i < MAXN; i++)
    	{
    		if (!isprime.test(i))
    		{
    			prime[++k] = i;
    			for (int j = i+i; j < MAXN; j+=i)
    			{
    				isprime.set(j);
    			}
    		}
    	}
    }