【数据结构】位图

- 日理万妓 2022-05-27 06:07 255阅读 0赞

位图（bitmap)，就是用每一位存放某种状态，适用于数据较多，且状态不多的情况。在Linux系统中，用位图来表示是否接收到进程发送的信号，接收到信号则将相关的比特位置1。

给出40亿个不重复的无符号整数，没排过序；在给定一个无符号的整数，判断这个数是不是在这40亿个数中。  
这道题的解决方法也用到了位图，一个无符号的整数能表示的最大的值是2^32=42亿多，每一个无符号的整数占用4个字节，那么40亿个数据如果全部放在内存中需要16G，这显然是一般计算机做不到的。可以想到，一个数据要么存在，要么不存在，只有两种状态，因此，我们不妨使用比特位来存储这些数，存在的置为1，不存在的置为0。一个int类型占32位，存储这些数据大概需要500M，这个数据一般的计算机是可以接受的。这样，就可以判断这个数是不是在这40亿个数据中。

位图的优点是可以存储较多的数据，很适合解决上述类型的题目；缺点是是可读性差。

位图的主要操作都有：

1.  置1操作
2.  恢复为0
3.  检测一个数是0还是1
4.  位图中1的个数
5.  位图中的总位数

下面来看一下位图的具体实现：

#include <iostream>
    #include <vector>
    using namespace std;
    
    class BitMap
    {
    public:
        BitMap(size_t bitSet = 10)
            : _bitCount(bitSet)
        {
            _bitSet.resize((bitSet >> 5) + 1);//右移5位，就是除以32，将bit的位数转成字节数
        }
        void Set(size_t whichBit) //置1
        {
            size_t index = whichBit >> 5;
            if (whichBit < _bitCount)
                _bitSet[index] |= 1 << (whichBit % 32);//A|0=A 0|1=1
        }
        void ReSet(size_t whichBit) //恢复0
        {
            size_t index = whichBit >> 5;
            if (whichBit < _bitCount)
                _bitSet[index] &= ~(1 << (whichBit % 32));//A&1=A 1&0=0   
                                     //也可以用异或：相同为0，相异为1  A^0=A 1^1=0
        }
        bool Test(size_t whichBit)//0返回0,1返回非0
        {
            size_t index = whichBit >> 5;
            if (whichBit < _bitCount)
                return _bitSet[index] & (1 << (whichBit % 32));//0&1=0 1&1=1
            cout << "比特位不存在" << endl;
            return false;
        }
        size_t Count()const //1的个数 
        {
            char* pBitCount = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4";
            size_t count = 0;
            for (size_t i = 0; i < _bitSet.size(); i++)
            {
                int value = _bitSet[i];
                int j = 0;
                while (j < sizeof(int))//j<4  一次一个字节
                {
                    count += pBitCount[value & 0x0F]; //取低四位 & 0000 1111
                    value >>= 4;
                    count += pBitCount[value & 0x0F]; //再取四位
                    value >>= 4;
                    j++;
                }
            }
            return count;
        }
        size_t Size()const
        {
            return _bitCount;
        }
    private:
        vector<int> _bitSet;
        size_t _bitCount;
    };
    
    void test()
    {
        BitMap bmp(50);
        bmp.Set(20);
        bmp.Set(40);
        bmp.Set(40);
        bmp.Set(15);
        bmp.Set(60);
        if (bmp.Test(10))
            cout << "第10位是1" << endl;
        else
            cout << "第10位是0" << endl;
    
        cout << "bit位数" << bmp.Size() << endl;
        cout << "bit位1的个数" << bmp.Count() << endl;
    
        bmp.ReSet(40);
        cout << "bit位1的个数" << bmp.Count() << endl;
    }
    int main()
    {
        test();
        return 0;
    }

运行结果：  
![这里写图片描述][70]

[70]: /images/20220527/273e0f2e49894f158d3c27c11e1a3948.png