【数据结构】位图

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

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

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

位图的主要操作都有：

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

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

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

运行结果：

【数据结构】位图

猜你在找的数据结构相关文章