<C++> STL_bitset使用和模拟实现

bitset的介绍

位图的引入

给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中?

要判断一个数是否在某一堆数中,我们可能会想到如下方法:

  • 将这一堆数进行排序,然后通过二分查找的方法判断该数是否在这一堆数中。
  • 将这一堆数插入到unordered_set容器中,然后调用find函数判断该数是否在这一堆数中。

单从方法上来看,这两种方法都是可以,而且效率也不错,第一种方法的时间复杂度是O(N*LogN),第二种方法的时间复杂度是O(N)。

但问题是这里有40亿个数,若是我们要将这些数全部加载到内存当中,那么将会占用16G的空间,空间消耗是很大的。因此从空间消耗来看,上面这两种方法实际都是不可行的。

位图解决

实际在这个问题当中,我们只需要判断一个数在或是不在,即只有两种状态,那么我们可以用一个比特位来表示数据是否存在,如果比特位为1则表示存在,比特位为0则表示不存在。比如:

在这里插入图片描述

无符号整数总共有2的32次方个,因此记录这些数字就需要2的32次方个比特位,也就是512M的内存空间,内存消耗大大减少。

位图的概念

所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。

位图的应用

常见位图的应用如下:

  1. 快速查找某个数据是否在一个集合中。
  2. 排序。
  3. 求两个集合的交集、并集等。
  4. 操作系统中磁盘块标记。
  5. 内核中信号标志位(信号屏蔽字和未决信号集)。

bitset的使用

bitset是一种特殊的容器类,它的每个元素只占用一位,只能为0或1。

bitset的定义方式

创建bitset对象,你可以直接指定它的大小,或者使用一个无符号长整型数或字符串初始化它:

方式一: 构造一个16位的位图,所有位都初始化为0。

bitset<16> bs1; //0000000000000000

方式二: 构造一个16位的位图,根据所给值初始化位图的前n位。

bitset<16> bs2(0xfa5); //0000111110100101

方式三: 构造一个16位的位图,根据字符串中的0/1序列初始化位图的前n位。

bitset<16> bs3(string("10111001")); //0000000010111001

bitset成员函数的使用

bitset类提供了以下一些常用的成员函数:

  • set:将bitset中的一位或所有位设置为1
  • reset:将bitset中的一位或所有位设置为0
  • flip:翻转bitset中的一位或所有位
  • test:获取指定位的状态
  • count:返回bitset中1的个数
  • size:返回bitset中位的个数
  • any:如果bitset中至少有一位为1,则返回true
  • none:如果bitset中所有位都为0,则返回true
  • all:如果所有位都被设置,则返回true
  • to_string:将bitset转换为字符串
  • to_ulongto_ullong:将bitset转换为无符号(长)整型数

使用示例:

#include <bitset>
#include <iostream>
using namespace std;

int main() {
    bitset<8> bs;
    //位置从0开始
    bs.set(2);         //设置第2位
    bs.set(4);         //设置第4位
    cout << bs << endl;//00010100

    bs.flip();                 //反转所有位
    cout << bs << endl;        //11101011
    cout << bs.count() << endl;//6

    cout << bs.test(3) << endl;//1  3的位置为1

    bs.reset(0);       //清空第0位,第0位变成了0
    cout << bs << endl;//11101010

    bs.flip(7);        //反转第7位
    cout << bs << endl;//01101010

    cout << bs.size() << endl;//8

    cout << bs.any() << endl;//任何位为1,就返回true 1

    bs.reset();               //清空所有位
    cout << bs.none() << endl;//没有位被设置,就返回true 1
 
    bs.set();                //设置所有位
    cout << bs.all() << endl;//所有位被设置,返回true  1

    return 0;
}22211

注意: 使用成员函数set、reset、flip时,若指定了某一位则操作该位,若未指定位则操作所有位。

bitset运算符的使用

一、bitset中>>、<<运算符的使用。
bitset容器对>>、<<运算符进行了重载,我们可以直接使用>>、<<运算符对biset容器定义出来的对象进行输入输出操作。

#include <iostream>
#include <bitset>
using namespace std;

int main() {
    bitset<8> bs;
    cin >> bs;         //10110
    cout << bs << endl;//00010110
    return 0;
}

二、bitset中赋值运算符、关系运算符、复合赋值运算符、单目运算符的使用。

bitset容器中不仅对赋值运算符和一些关系运算符进行了重载,而且对一些复合赋值运算符和单目运算符也进行了重载,我们可以直接使用这些运算符对各个位图进行操作。

包括如下运算符:

  • 赋值运算符:=。
  • 关系运算符:==、!=。
  • 复合赋值运算符:&=、|=、^=、<<=、>>=。
  • 单目运算符:~。

三、bitset中位运算符的使用。
bitset容器中同时也对三个位运算符进行了重载,我们可以直接使用&、|、^对各个位图进行操作。

#include <bitset>
#include <iostream>
#include <string>
using namespace std;

int main() {
    bitset<8> bs1(string("10101010"));
    bitset<8> bs2(string("01010101"));

    cout << (bs1 & bs2) << endl;//00000000
    cout << (bs1 | bs2) << endl;//11111111
    cout << (bs1 ^ bs2) << endl;//11111111
    return 0;
}

四、bitset中[ ]运算符的使用。
bitset容器中对[ ]运算符进行了重载,我们可以直接使用[ ]对指定位进行访问或修改。

#include <bitset>
#include <iostream>
#include <string>
using namespace std;

int main() {
    bitset<8> bs(string("00110101"));
    cout << bs[0] << endl;//1
    bs[0] = 0;
    cout << bs << endl;//00110100
    return 0;
}

bitset的模拟实现

bit类各函数接口总览

namespace cl {
    //模拟实现位图
    template<size_t N>
    class bitset {
    public:
        //构造函数
        bitset();
        //设置位
        void set(size_t pos);
        //清空位
        void reset(size_t pos);
        //反转位
        void flip(size_t pos);
        //获取位的状态
        bool test(size_t pos);
        //获取可以容纳的位的个数
        size_t size();
        //获取被设置位的个数
        size_t count();
        //判断位图中是否有位被设置
        bool any();
        //判断位图中是否全部位都没有被设置
        bool none();
        //判断位图中是否全部位都被设置
        bool all();
        //打印函数
        void Print();

    private:
        vector<int> _bits;//位图
    };
}// namespace cl

bitset类的实现

构造函数

在构造位图时,我们需要根据所给位数N,创建一个N位的位图,并且将该位图中的所有位都初始化为0。

一个整型有32个比特位,因此N个位的位图就需要用到N/32个整型,但是实际我们所需的整型个数是N/32+1,因为所给非类型模板参数N的值可能并不是32的整数倍。

例如,当N为40时,我们需要用到两个整型,即40/32+1=2。

在这里插入图片描述

代码如下:

//构造函数
bitset(){
	_bits.resize(N / 32 + 1, 0);
}

成员函数

set

set成员函数用于设置位。

设置位图中指定的位的方法如下:

  1. 计算出该位位于第 i 个整数的第 j 个比特位。

  2. 将1左移 j 位后与第 i 个整数进行或运算即可。

    在这里插入图片描述

代码如下

//设置位
void set(size_t pos){
	assert(pos < N);

	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
	_bits[i] |= (1 << j); //将该位设置为1(不影响其他位)
}
reset

reset成员函数用于清空位。

清空位图中指定的位的方法如下:

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。

在这里插入图片描述

代码如下

//清空位
void reset(size_t pos){
	assert(pos < N);

	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
	_bits[i] &= (~(1 << j)); //将该位设置为0(不影响其他位)1进行翻转后只有第j位置位0 其他都是1,所以只会影响第j位置的数字
}
flip

flip成员函数用于反转位。

反转位图中指定的位的方法如下:

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位后与第 i 个整数进行异或运算即可。

在这里插入图片描述

代码如下

//反转位
void flip(size_t pos){
	assert(pos < N);

	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
	_bits[i] ^= (1 << j); //将该进行反转(不影响其他位)
}
test

test成员函数用于获取位的状态。

获取位图中指定的位的状态的方法如下:

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位后与第 i 个整数进行与运算得出结果。
  3. 若结果非0,则该位被设置,否则该位未被设置。

在这里插入图片描述

代码如下

//获取位的状态
bool test(size_t pos){
	assert(pos < N);

	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
	//该比特位被设置
	if (_bits[i] & (1 << j)){
		return true;
	} else {//该比特位未被设置
		return false;
	} 
}
size、count

size成员函数用于获取位图中可以容纳的位的个数。

我们直接将所给非类型模板参数进行返回即可。

//获取可以容纳的位的个数
size_t size(){
	return N;
}

count成员函数用于获取位图中被设置的位的个数。

获取位图中被设置的位的个数,也就是统计位图中1的个数,我们只需要依次统计每个整数二进制中1的个数,然后将其相加即可得到位图中1的个数。

统计二进制中1的个数的方法如下:

  1. 将原数n与n - 1进行与运算得到新的 n 。
  2. 判断n是否为0,若 n 不为0则继续进行第一步。

如此进行下去,直到n最终为0,此时该操作进行了几次就说明二进制中有多少个1。

因为该操作每进行一次就会消去二进制中最右边的1

代码如下

//获取被设置位的个数
size_t count(){
	size_t count = 0;
	//将每个整数中1的个数累加起来
	for (auto e : _bits){
		int num = e;
		//计算整数num中1的个数
		while (num){
			num = num&(num - 1);
			count++;
		}
	}
	return count; //位图中1的个数,即被设置位的个数
}
any、none、all

any成员函数用于判断位图中是否有位被设置。

我们只需遍历每一个整数,若这些整数全部都为0,则说明位图中没有位被设置过。
虽然位图可能并没有包含最后一个整数的全部比特位,但由于我们构造位图时是将整数的全部比特位都初始化成了0,因此不会对此处判断造成影响。

在这里插入图片描述

代码如下

//判断位图中是否有位被设置
bool any(){
	//遍历每个整数
	for (auto e : _bits){
		//该整数中有位被设置
		if (e != 0) {
			return true;
		}		
	}
	return false; //全部整数都是0,则没有位被设置过
}

none成员函数用于判断位图中是否全部位都没有被设置。

位图中是否全部位都没有被设置,实际上就是位图中有位被设置的反面,因此none成员函数直接调用any成员函数,然后将返回值取反后再进行返回即可。

//判断位图中是否全部位都没有被设置
bool none() {
	return !any();
}

all成员函数用于判断位图中是否全部位都被设置。

判断过程分为两步:

  1. 先检查前n-1个整数的二进制是否为全1。
  2. 再检查最后一个整数的前N%32个比特位是否为全1。

需要注意的是,如果位图没有包含最后一个整数的全部比特位,那么最后一个整数的二进制无论如何都不会为全1,所以在判断最后一个整数时应该只判断位图所包含的比特位。

在这里插入图片描述

代码如下

//判断位图中是否全部位都被设置
bool all() {
    size_t n = _bits.size();
    //先检查前n-1个整数
    for (size_t i = 0; i < n - 1; i++) {
        //取反后不为全0,说明取反前不为全1
        if (~_bits[i] != 0){
            return false;
        }
    }
    //再检查最后一个整数的前N%32位
    for (size_t j = 0; j < N % 32; j++) {
        //等于0表示没有被设置
        if ((_bits[n - 1] & (1 << j)) == 0){
            return false;
        }
    }
    return true;
}

打印函数

可以实现一个打印函数,便于检查我们上述代码的正确性,打印位图时遍历位图所包含的比特位进行打印即可,在打印位图的过程中可以顺便统计位图中位的个数count,将count与我们传入的非类型模板参数N进行比较,可以判断位图大小是否是符合我们的预期。文章来源地址https://www.uudwc.com/A/woq2O/

//打印函数
void Print() {
    int count = 0;
    size_t n = _bits.size();
    //先打印前n-1个整数
    for (size_t i = 0; i < n - 1; i++) {
        for (size_t j = 0; j < 32; j++) {
            if (_bits[i] & (1 << j)) {
                cout << "1";
            } else {
                cout << "0";
            }
            count++;
        }
    }
    //再打印最后一个整数的前N%32位
    for (size_t j = 0; j < N % 32; j++) {
        if (_bits[n - 1] & (1 << j)){
            cout << "1";
        }
        else{
            cout << "0";
        }
        count++;
    }
    cout << " " << count << endl;//打印总共打印的位的个数
}

原文地址:https://blog.csdn.net/ikun66666/article/details/133501681

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年10月27日 22:08
贪心算法+练习
下一篇 2023年10月27日 23:08