【数据结构】位图

位图(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;
}

运行结果:
这里写图片描述

相关文章
相关标签/搜索