«

怎么使用C++实现位图处理

时间:2024-6-10 11:15     作者:韩俊     分类: Java


今天小编给大家分享一下怎么使用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判断是否有位被设置&ndash;>如果有任何一个位被设置则返回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;
}

标签: java

热门推荐