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

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

关键知识点

  • 位向量可以简单地理解为用二进制位的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可以直接看下面代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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
2
3
4
1.面试时碰到一个投票的题,有几十亿个人要投票,有5个候选人。一个人如果投过票之后就不能再投了,所以需要标记谁投过票,便可以用位图来节省空间。
引用:
2.Linux中分配唯一pid的算法、内存管理的伙伴分配系统等,详细可以google,关键词:linux+位图。
3.一个最多包含n个正整数的文件,每个数都小于n,其中n=107,并且没有重复。最多有1MB内存可用。要求用最快方式将它们排序并按升序输出。(《编程珠玑》第一章正文)方法是一次读入文件,把出现过的数字对应位置1;读取完毕后从低位到高位输出位向量为1的位所代表的数。

参考

欢迎与我分享你的看法。
转载请注明出处:http://taowusheng.cn/