bitset（位图）的使用与模拟实现

bitset（位图）

    • 位图引入
    • bitset的使用
    • bitset（位图）的模拟实现
      • bitset类各函数接口总览
      • bitset类的实现
        • 构造函数
        • set、reset、flip、test
        • size、count
        • any、none、all
        • 打印函数

位图引入

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

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

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

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

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

位图解决

实际在这个问题当中，我们只需要判断一个数在或是不在，即只有两种状态，那么我们可以用一个比特位来表示数据是否存在，如果比特位为1则表示存在，比特位为0则表示不存在。比如：
在这里插入图片描述
无符号整数总共有232个，因此记录这些数字就需要232个比特位，也就是512M的内存空间，内存消耗大大减少。

位图的概念

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

位图的应用

常见位图的应用如下：

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

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设置指定位或所有位
reset清空指定位或所有位
flip反转指定位或所有位
test获取指定位的状态
count获取被设置位的个数
size获取可以容纳的位的个数
any如果有任何一个位被设置则返回true
none如果没有位被设置则返回true
all如果所有位都被设置则返回true

使用示例：

#include <iostream>
#include <bitset>//注意引入头文件
using namespace std;

int main()
{
	bitset<8> bs;
	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

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

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

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

	cout << bs.any() << endl; //1

	bs.reset(); //清空所有位
	cout << bs.none() << endl; //1

	bs.set(); //设置所有位
	cout << bs.all() << endl; //1
	return 0;
}

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

bitset运算符的使用

1、bitset中>>、<<运算符的使用。

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

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

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

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

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

包括如下运算符：

  • 赋值运算符：=。
  • 关系运算符：==、!=。
  • 复合赋值运算符：&=、|=、^=、<<=、>>=。
  • 单目运算符：~。
#include <iostream>
#include <string>
#include <bitset>
using namespace std;

int main()
{
	bitset<8> bs1(string("10101010"));
	bitset<8> bs2(string("10101010"));
	bs1 >>= 1;
	cout << bs1 << endl; //01010101

	bs2 |= bs1;
	cout << bs2 << endl; //11111111
	return 0;
}

3、bitset中位运算符的使用。

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

#include <iostream>
#include <string>
#include <bitset>
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;
}

4、bitset中[ ]运算符的使用。

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

#include <iostream>
#include <string>
#include <bitset>
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（位图）的模拟实现

bitset类各函数接口总览

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; //位图
	};
}

注：为了防止与标准库当中的bitset类产生命名冲突，模拟实现时需放在自己的命名空间当中。

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、reset、flip、test

set

set成员函数用于设置位。

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

  • 计算出该位位于第 i 个整数的第 j 个比特位。
  • 将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成员函数用于清空位。

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

  • 计算出该位位于第 i 个整数的第 j 个比特位。
  • 将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（不影响其他位）
}
//注意： ！-> 逻辑取反
//      ~ -> 按位取反

flip

flip成员函数用于反转位。

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

  • 计算出该位位于第 i 个整数的第 j 个比特位。
  • 将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成员函数用于获取位的状态。

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

  • 计算出该位位于第 i 个整数的第 j 个比特位。
  • 将1左移 j 位后与第 i 个整数进行与运算得出结果。
  • 若结果非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成员函数用于获取位图中可以容纳的位的个数。

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

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

count

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

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

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

  • 将原数 n 与 n - 1 进行与运算得到新的 n 。
  • 判断 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

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

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

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

none

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

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

代码:

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

all

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

判断过程分为两步：

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

需要注意的是，如果位图没有包含最后一个整数的全部比特位，那么最后一个整数的二进制无论如何都不会为全1，所以在判断最后一个整数时应该只判断位图所包含的比特位。
在这里插入图片描述
代码：

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

打印函数

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

//打印函数
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; //打印总共打印的位的个数
}

The end

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/14284.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

AlgoC++第三课：C++世界观

AlgoC++第三课：C++世界观

目录 C世界观前言1. 程序逻辑2. 内存的逻辑3. 调度的逻辑4. 编译的逻辑5. 作用域的逻辑6. 命名空间的逻辑7. 生命周期的逻辑8. C类的逻辑9. 编译时和运行时的逻辑总结 C世界观 前言 手写AI推出的全新面向AI算法的C课程 Algo C&#xff0c;链接。记录下个人学习笔记&#xff0c…
阅读更多...
Vue+Vant封装通用模态框单选框组件

Vue+Vant封装通用模态框单选框组件

前言 我们知道&#xff0c;在vant组件中提供的组件往往是比较基础的&#xff0c;能够满足基本需求。但是我们想实现ui设计的一些比较丰富效果的组件&#xff0c;需要自己去实现&#xff0c;且当项目中多次用到的时候&#xff0c;我们将以组件化的思想将其封装起来&#xff0c;…
阅读更多...
Linux服务器出现503 服务不可用错误怎么办？

Linux服务器出现503 服务不可用错误怎么办？

​　　HTTP 503 服务不可用错误代码表示网站暂时不可用。无论您是网站访问者还是管理员&#xff0c;503 页面都很麻烦。尽管该错误表明存在服务器端问题&#xff0c;但对于访问者和网络管理员来说&#xff0c;有一些可能的解决方案。本文将解释Linux服务器出现503 服务不可用错…
阅读更多...
scratch足球射门练习 中国电子学会图形化编程 少儿编程 scratch编程等级考试一级真题和答案解析2023年3月

scratch足球射门练习 中国电子学会图形化编程 少儿编程 scratch编程等级考试一级真题和答案解析2023年3月

目录 scratch足球射门练习 一、题目要求 1、准备工作 2、功能实现 二、案例分析
阅读更多...
【网络安全】红队基础免杀

【网络安全】红队基础免杀

引言 本文主要介绍“反射型 dll 注入”及“柔性加载”技术。 反射型 dll 注入 为什么需要反射型 dll 注入 常规的 dll 注入代码如下&#xff1a; int main(int argc, char *argv[]) {HANDLE processHandle;PVOID remoteBuffer;wchar_t dllPath[] TEXT("C:\\experime…
阅读更多...
分享几个国内免费的ChatGPT镜像网址(亲测有效-4月25日更新)

分享几个国内免费的ChatGPT镜像网址(亲测有效-4月25日更新)

最近由于ChatGPT的爆火也让很多小伙伴想去感受一下ChatGPT的魅力&#xff0c;那么今天就分享几个ChatGPT国内的镜像网址&#xff0c;大家可以直接使用&#xff01;记得点赞收藏一下呦&#xff01; 1、AQ Bot&#xff0c;网址&#xff1a;点我 https://su.askaiw.com/aq 缺点&…
阅读更多...
面试篇：Redis

面试篇：Redis

一、缓存穿透 1、缓存穿透 查询一个不存在的数据&#xff0c;mysql查询不到数据也不会直接写入缓存&#xff0c;就会导致每次请求都查数据库。即&#xff1a;大量请求根本不存在的key 2、查询流程 3、出现原因 业务层误将缓存和库中的数据删除了&#xff0c;也可能是有人恶…
阅读更多...
JUC-多线程（12. AQS-周阳）学习笔记

JUC-多线程（12. AQS-周阳）学习笔记

文章目录 1. 可重入锁1.1. 概述1.2. 可重入锁类型1.3. Synchronized 可重入实现机理 2. LockSupport2.1. LockSupport 是什么2.2. 3种线程等待唤醒的方法2.2.1 Object 的等待与唤醒2.2.2. Condition接口中的等待与唤醒2.2.3. 传统的 synchronized 和 Lock 实现等待唤醒通知的约…
阅读更多...
【手把手做ROS2机器人系统开发一】开发环境搭建

【手把手做ROS2机器人系统开发一】开发环境搭建

【手把手做ROS2机器人系统开发一】开发环境搭建 目录 【手把手做ROS2机器人系统开发一】开发环境搭建 一、专栏介绍&#xff1a; 二、开发环境搭建&#xff1a; 1.Ubuntu系统安装 2.ROS2系统环境安装 3.测试系统运行 一、专栏介绍&#xff1a; 大家好&#xff0c;今天给大家…
阅读更多...
栈的基本操作（C语言实现）创建，销毁，入栈，出栈

栈的基本操作（C语言实现）创建，销毁，入栈，出栈

前言 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原则。 压栈&#xff1a;栈的…
阅读更多...
同样是测试，朋友到了30k，我才12K，这份测试面试8股文确实牛

同样是测试，朋友到了30k，我才12K，这份测试面试8股文确实牛

程序猿在世人眼里已经成为高薪、为人忠诚的代名词。 然而&#xff0c;小编要说的是&#xff0c;不是所有的程序员工资都是一样的。 世人所不知的是同为程序猿&#xff0c;薪资的差别还是很大的。 众所周知&#xff0c;目前互联网行业是众多行业中薪资待遇最好的&#xff0c;…
阅读更多...
Fedora 38 正式发布

Fedora 38 正式发布

Fedora Linux 38 正式发布&#xff0c;用户可以访问官网下载安装最新版本。 新网站 如果你点击了上面的官网链接&#xff0c;你应该会注意到 Fedora 的官网看起来与之前有了很大不同。这是 Fedora Websites & Apps 团队与 Design & Infrastructure 团队以及广大社区合作…
阅读更多...
【视频课程】算法工程师需要的ChatGPT大模型算法理论与实践课程！非粗浅科普...

【视频课程】算法工程师需要的ChatGPT大模型算法理论与实践课程！非粗浅科普...

前言 自从2022年11月ChatGPT发布之后&#xff0c;迅速火遍全球。其对话的交互方式&#xff0c;能够回答问题&#xff0c;承认错误&#xff0c;拒绝不适当的请求&#xff0c;高质量的回答&#xff0c;极度贴近人的思维的交流方式&#xff0c;让大家直呼上瘾&#xff0c;更是带火…
阅读更多...
安装配置SVN版本控制管理工具

安装配置SVN版本控制管理工具

SVN工具能帮我们做什么&#xff1f; 核心功能&#xff1a;文档版本管理系统 适合对象&#xff1a;个人与团队都可以使用&#xff0c;企业中项目资源的重要管理工具 举例&#xff1a;一个文件夹里面的文档管理 1.下载安装SVN服务器 VisualSVN-Server 2.下载安装SVN客户端 T…
阅读更多...
＜网络编程＞网络套接字

＜网络编程＞网络套接字

目录 理解源IP地址和目的IP地址 认识端口号 端口号和进程ID的关系 理解源端口号和目的端口号 初步认识TCP、UDP协议 TCP协议 UDP协议 网络字节序列 socket网络接口 socket常见API sockaddr结构 UDPsocket 编码&#xff1a; 理解源IP地址和目的IP地址 源IP&#xf…
阅读更多...
Jupyter Notebook的安装与使用

Jupyter Notebook的安装与使用

Jupyter Notebook Jupyter Notebook介绍Jupyter Notebook使用安装启动创建文件编写代码和文本常用命令配置文件 Anaconda Jupyter Notebook介绍 Jupyter Notebook是一个基于Web的交互式计算环境&#xff0c;可以让用户以文档形式记录代码、数据分析结果和说明文本&#xff0c;并…
阅读更多...
从零开始的ChatGLM 配置详细教程

从零开始的ChatGLM 配置详细教程

从零开始的ChatGLM配置教程 文章目录 从零开始的ChatGLM配置教程一&#xff0c;前言二&#xff0c;环境配置1、下载ChatGLM项目2、配置程序运行环境 三、在HuggingFace下载chatGLM-6B模型1&#xff0c;安装 Git Lfs2&#xff0c;下载相关文件3&#xff0c;在HuggingFace中下载相…
阅读更多...
一致性 Hash 算法 及Java TreeMap 实现

一致性 Hash 算法 及Java TreeMap 实现

1、一致性 Hash 算法原理 一致性 Hash 算法通过构建环状的 Hash 空间替线性 Hash 空间的方法解决了这个问题&#xff0c;整个 Hash 空间被构建成一个首位相接的环。 其具体的构造过程为&#xff1a; 先构造一个长度为 2^32 的一致性 Hash 环计算每个缓存服务器的 Hash 值&…
阅读更多...
基于Java+Spring+vue+element实现旅游信息管理平台系统

基于Java+Spring+vue+element实现旅游信息管理平台系统

基于JavaSpringvueelement实现旅游信息管理平台系统 博主介绍&#xff1a;5年java开发经验&#xff0c;专注Java开发、定制、远程、指导等,csdn特邀作者、专注于Java技术领域 作者主页 超级帅帅吴 Java项目精品实战案例《500套》 欢迎点赞 收藏 ⭐留言 文末获取源码联系方式 文…
阅读更多...
抢先看，甘特图工具DHTMLX gantt 灯箱编辑器通过套件 UI 小部件进行了扩展

抢先看，甘特图工具DHTMLX gantt 灯箱编辑器通过套件 UI 小部件进行了扩展

DHTMLX Gantt是用于跨浏览器和跨平台应用程序的功能齐全的Gantt图表。可满足项目管理应用程序的大部分开发需求&#xff0c;具备完善的甘特图图表库&#xff0c;功能强大&#xff0c;价格便宜&#xff0c;提供丰富而灵活的JavaScript API接口&#xff0c;与各种服务器端技术&am…
阅读更多...
最新文章

Copyright @ 2022~2023