如何用Cpp实现一个BitMap位向量

yifei_

发布于 2022-11-14 14:30:56

6630

发布于 2022-11-14 14:30:56

文章被收录于专栏：yifei的专栏

《编程珠玑》在第一章就介绍了位图/位向量的知识点，这一技术也有许多应用场景。

关键知识点

位向量可以简单地理解为用二进制位的01来实现bool类型的功能。
当给数组去重，无重复元素的数组排序时，一般会开一个int数组或者bool数组，但即使是bool数组，在c语言中的也是要占用2个字节(8位)。
利用位运算符，我们可以使用二进制位的零一来表示数据的有无，这样只花费bool数组的1/8地内存就够了。
用int数组来作基本的存储类型时，1个int变量有32位，可以存储32个数据。
1到32就可以存在第一个int，33到64可以存储在第二个int，那n/32就可以得知第n个bit位存在第几个int上，用位运算表示n>>5.
n%32可以改为n&(0x00011111)，也就是n&(0x1f).
设置shift=5，mask=0x1f,set和get可以直接看下面代码。

#include <iostream>
#include <vector>

using namespace std;

class BitMap{
public:
    BitMap(int n):bitlen(n),intlen((bitlen>>shift)+1),shift(5),mask(0x1F),bitmap(intlen,0) {}
    void clr(){ fill(bitmap.begin(),bitmap.end(),0); }
    void set(int n){ bitmap[n>>shift] |= (1<<(n&mask)); }
    bool get(int n) { return bitmap[n>>shift] & (1<<(n&mask)); }

private:
    int bitlen;
    int intlen;
    const int shift;
    const int mask;
    vector<unsigned int> bitmap;
};

int main() {
    vector<int> vi={1,3,9,2,7,19};
    BitMap bitmap(20);
    bitmap.clr();
    for(int i=0;i<20;i++){
        cout<<bitmap.get(i)<<" ";
    }
    cout<<endl;
    for(int i=0;i<vi.size();i++){
        bitmap.set(vi[i]);
        cout<<bitmap.get(vi[i])<<endl;
    }
    for(int i=0;i<20;i++){
        cout<<bitmap.get(i)<<" ";
    }
    return 0;
}

应用

1.面试时碰到一个投票的题，有几十亿个人要投票，有5个候选人。一个人如果投过票之后就不能再投了，所以需要标记谁投过票，便可以用位图来节省空间。
引用：
2.Linux中分配唯一pid的算法、内存管理的伙伴分配系统等，详细可以google，关键词：linux+位图。
3.一个最多包含n个正整数的文件，每个数都小于n，其中n=107，并且没有重复。最多有1MB内存可用。要求用最快方式将它们排序并按升序输出。（《编程珠玑》第一章正文）方法是一次读入文件，把出现过的数字对应位置1；读取完毕后从低位到高位输出位向量为1的位所代表的数。