今天小编给大家分享一下怎么使用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;
}