使用C++实现位图处理
位图的引入
无序的40亿个不重复的无符号整数,给一个无符号整数,如何判断一个数是否在这40亿个数中
方法1:遍历, 时间复杂度O(N)
方法2:排序—O(N*logN) + 二分查找----O(logN)
方法3:可以将所有数放到unordered_set中,然后调用find函数查找
上述的方法存在的问题:
- 这里有40亿个数, 若是我们要将这些数全部加载到内存当中,那么将会占用16G的空间,空间消耗是很大的
- 因此从空间消耗来看,上述的方法都是不可行的
方法4:利用位图解决
无符号整数总共有2^32个,因此记录这些数字就需要2^32个比特位,仅仅需要512M的内存空间,内存消耗大大减少
问:40亿个整数需要占用多少空间
1G =1024*1024*1024 Byte = 10亿字节,刚才存放一个整形4个字节,32个比特位,需要16G的空间,现在用一个比特位存,只需要16/32 = 0.5G即可
注意我们需要开辟42亿9千多万个比特位,而不是40亿个比特位,因为要映射,要按照整数的最大范围去开,而不是按个数去开 开辟内存的最小单位->字节->用char/int都可以
如何正确开辟42亿9前多万个比特位呢?
共有两种方式: bitset: template<size_t N> class bitset;
bitset<0xffffffff> bs;//#define UINT_MAX 0xffffffff
bitset<-1> bs; //-1的补码是全1 0xffffffff,而非类型模板参数的N的参数是size_t类型
什么是位图
所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景,通常是用来判断某个数据存不存在的
数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在
例子:
位图的应用
- 快速查找某个数据是否在一个集合中
- 排序
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
- 内核中信号标志位（信号屏蔽字和未决信号集）
bitset的使用
定义方式
bitset ---> template <size_t N> class bitset; 位图的大小在编译时是固定的（由其模板参数确定)
- 构造一个N位的位图,所有位都初始化为0
- 构造一个N位的位图,根据所给值初始化位图的前n位
- 构造一个N位的位图,根据字符串中的0/1序列初始化位图的前n位
#include<bitset>
int main()
{
//方式1:构造一个N位的位图,所有位都初始化为0
bitset<16> bs1;//0000 0000 0000 0000
//方式2:构造一个N位的位图,根据所给值初始化位图的前n位
bitset<16> bs2(0xabc);//0011 1101 0101 0000
//方式3:构造一个N位的位图,根据字符串中的0/1序列初始化位图的前n位
bitset<16> bs3(string("10110001"));//1000 1101 0000 0000
return 0;
}
成员函数
| 成员函数 | 功能 |
|---|---|
| set | 设置指定位或所有位为1 |
| reset | 清空指定位或所有位为0 |
| flip | 反转指定位或所有位 |
| test | 获取指定位的状态 0或者1 |
| count | 获取被设置位的个数 |
| size | 获取可以容纳的位的个数 |
| any | 判断是否有位被设置–>如果有任何一个位被设置则返回true |
| none | 判断是否所有位都没有被设置->如果没有位被设置则返回true |
| all | 判断是否所有位都设置->如果所有位都被设置则返回true |
使用实例:
#include<iOStream>
#include<bitset>
int main()
{
//从右到左算起, 最右边为第0位
bitset<8> bs;//构造一个8位的位图,所有位都初始化为0
bs.set(1);//设置第1位为1
bs.set(5);//设置第5位为1
cout << bs << endl; //00100010
bs.flip();//反转bs的所有位
cout << bs << endl;//11011101
cout << "共有"<<bs.count()<<"位被设置成1" << endl;//共有6位被设置成1
cout << bs.test(3) << endl;//输出第3位的状态 - 1
bs.reset(1);//将第1位设置为0
cout << bs << endl;//11011101
bs.flip(7);//将第7位反转
cout << bs << endl;//01011101
cout << bs.size() << endl;//输出位图可以容纳的位的个数 ---8
cout << bs.any() << endl;//判断是否有位被设置 ---1
bs.reset();//清空所有位
cout << bs << endl;//00000000
bs.set();//将所有位设置为1
cout << bs << endl;//11111111
cout << bs.all() << endl;//判断是否所有位都设置 ----1
return 0;
}
注意如何区分成员函数set,reset,flip是对所有位操作还是对某一个位操作呢?
如果成员函数带了参数,就是对该指定的位操作如果没有指定,就是对所有位操作
bitset的运算符重载
>> 及 << 运算符
我们可以直接使用>> 和 <<运算符对biset容器对应的所有位进行输入输出操作
如果输入的位数比位图所能容纳的位数N多,只会从前向后截取N位
#include<bitset>
int main()
{
bitset<8> bs;
cin >> bs;//输入:10101
cout << bs << endl;//00010101
return 0;
}
赋值-关系-复合赋值-单目运算符
bitset容器对一些复合赋值运算符和单目运算符也进行了重载
- 赋值运算符：
= - 关系运算符：
==!= - 复合赋值运算符：
&=|=^=<<=>>= - 单目运算符：
~
#include<bitset>
int main()
{
bitset<8> bs1(string("11111111"));
bitset<8> bs2(string("01010101"));
cout << bs1 << endl;//11111111
bs1 >>= 1;
cout << bs1 << endl;//01111111
bs2 &= bs1;
cout << bs2 << endl;//01010101
return 0;
}
其次我们可以使用& | ^ 对位图进行操作
#include<bitset>
int main()
{
bitset<8> bs1(string("10101111"));
bitset<8> bs2(string("01101101"));
cout << (bs1 | bs2) << endl;//11101111
cout << (bs1 & bs2) << endl;//00101101
cout << (bs1 ^ bs2) << endl;//11000010
return 0;
}
[]重载
bitset容器中对[ ]运算符进行了重载,我们可以直接使用[ ]对指定位进行访问或修改
int main()
{
bitset<8> bs(string("11001010"));
cout << bs[0] << endl; //0
bs[0] = 1;
cout << bs << endl; //11001011
return 0;
}
到此这篇关于使用c++实现位图处理的文章就介绍到这了,更多相关C++位图处理内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！
相关文章