《编程珠玑》在第一章就介绍了位图/位向量的知识点,这一技术也有许多应用场景。
#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的位所代表的数。
欢迎与我分享你的看法。 转载请注明出处:http://taowusheng.cn/