【数据结构】位图
发布时间:2020-12-15 06:34:25 所属栏目:安全 来源:网络整理
导读:位图(bitmap),就是用每一位存放某种状态,适用于数据较多,且状态不多的情况。在Linux系统中,用位图来表示是否接收到进程发送的信号,接收到信号则将相关的比特位置1。 给出40亿个不重复的无符号整数,没排过序;在给定一个无符号的整数,判断这个数是不
位图(bitmap),就是用每一位存放某种状态,适用于数据较多,且状态不多的情况。在Linux系统中,用位图来表示是否接收到进程发送的信号,接收到信号则将相关的比特位置1。 给出40亿个不重复的无符号整数,没排过序;在给定一个无符号的整数,判断这个数是不是在这40亿个数中。 位图的优点是可以存储较多的数据,很适合解决上述类型的题目;缺点是是可读性差。 位图的主要操作都有:
下面来看一下位图的具体实现: #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 = " 112122312232334";
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;
}
运行结果: (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- 从Scala枚举值中检索名称属性
- angularjs – 为什么ng-click不能在case-1中工作,但在case-
- 如何使用Twitter的Bootstrap popovers的jQuery验证通知?
- Angular 2上的Ngrx Store,Effects,Http Ajax轮询设置
- AngularJS之定时器(timeout)
- Scala iteratee写入文件
- 使用vim提取文本
- angularjs – angular – 更新指令模板点击
- twitter-bootstrap – 如何从bootstrap轮播中的glyphicons中
- Docker-compose无法在boot2docker上安装或正常运行