C++语法中bitset位图介绍及模拟实现
一、位图的引入
先来看下边一道面试题:
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。
经过我们之前的学习,我们可能会有以下的思路:
-
对这些数进行排序,再通过二分算法,查找这个数是否存在
-
插入到unordered_set中,使用find函数查找是否存在
上述方法看起来还不错,二分查找算法时间复杂度为logN,而插入到unordered_set中时间复杂度为O(N),而查找时时间复杂度为O(1),但是都有一个问题就是要将空间不足,40亿个无符号整形,需要160亿字节的空间,大概就是16GB的空间,一般计算机的内促都是4G或者8G,所以空间不足,此时就有了位图的方法来解决:
数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。比如:

对于上图来说,有一个整形数组,我们可以使用直接定址法对数组的数据进行映射,但是与之前不同的是,此时只是使用一个比特位来代表一个整形数据,当这个数存在时,比特位置1,不存在时,比特位置0,此时就可以大大节省空间资源,无符号整数只有2的32次方个,所以最多开2的32次方个空间,一个空间为一个比特,所以最终只需要512MB的空间。但是我们不能按照位来空间,最少必须一个字节,所以我们就每次开一个字节的空间,也就是8个比特位,将8位当做一个整体来处理,对要保存的数据除8就是第几个字节,对保存的数据模8就是在这个字节中的第几个位置。
二、位图的概念
所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。
那么位图还有哪些应用呢?
快速查找某个数据是否在一个集合中
排序 + 去重
求两个集合的交集、并集等
操作系统中磁盘块标记
位图模拟实现
一、构造函数
由于不能按位开空间,所以我们选择每次开一个字节的空间,由于有范围最大为N,一位关联一个数据,所以需要开N/8个字节的空间,但是有时可能不能整除,所以要开N/8+1个字节的空间。所以
直接在构造函数中开好空间:
bitset(){_bits.resize(N / 8 + 1,0);}
二、set,reset,test函数
set函数的作用是对位图中的某一位进行填充
i就表示是第几个字节,而j表示该位在该字节中的第几位,所以对1进行左移j位后与该字节按位或,按位或的作用时不论该位为0还是为1,都将该位变为1。

void set(size_t x){int i = x / 8;int j = x % 8;_bits[i] |= (1 << j);}
reset的作用是将某一位清空
同样的将要清空的那一位置为0,进行按位与,不论原本该位是0还是1,都将该位置0

void reset(size_t x){int i = x / 8;int j = x % 8;_bits[i] &= ~(1 << j);}
test的作用是检测位图中某一位是否存在

bool test(size_t x){int i = x / 8;int j = x % 8;return _bits[i] & (1 << j);}
三、代码测试
void test_bit_set1(){bitset<100> bs1;bs1.set(8);bs1.set(9);bs1.set(20);cout << bs1.test(8) << endl;cout << bs1.test(9) << endl;cout << bs1.test(20) << endl;bs1.reset(8);bs1.reset(9);bs1.reset(20);cout << bs1.test(8) << endl;cout << bs1.test(9) << endl;cout << bs1.test(20) << endl;}

四、完整代码
namespace tmt
{template<size_t N>class bitset{public:bitset(){_bits.resize(N / 8 + 1,0);}void set(size_t x){int i = x / 8;int j = x % 8;_bits[i] |= (1 << j);}void reset(size_t x){int i = x / 8;int j = x % 8;_bits[i] &= ~(1 << j);}bool test(size_t x){int i = x / 8;int j = x % 8;return _bits[i] & (1 << j);}private:vector<char> _bits;};void test_bit_set1(){bitset<100> bs1;bs1.set(8);bs1.set(9);bs1.set(20);cout << bs1.test(8) << endl;cout << bs1.test(9) << endl;cout << bs1.test(20) << endl;bs1.reset(8);bs1.reset(9);bs1.reset(20);cout << bs1.test(8) << endl;cout << bs1.test(9) << endl;cout << bs1.test(20) << endl;}

相关文章:
C++语法中bitset位图介绍及模拟实现
一、位图的引入 先来看下边一道面试题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 经过我们之前的学习,我们可能会有以下的思路: 对这些数进行排序ÿ…...
Debezium系列之:深入理解消息过滤,实现过滤数据库删除事件,只采集数据库新增和更新事件
Debezium系列之:深入理解消息过滤,实现过滤数据库删除事件,只采集数据库新增和更新事件 一、需求背景二、相关技术三、部署相关jar包四、参数详解五、总结一、需求背景 使用Debezium采集数据库数据,现在部分表只想采集新增数据和更新数据二、相关技术 实现这个需求的技术可…...
Substack 如何在去中心化内容创作领域掀起波澜
面对数字内容广告化的困境,Substack回归做内容的初心,通过产品和平台双轮驱动,重塑一个去中心化的多元文化内容聚集地,实现了增长突破。其核心策略在于先使用简洁的创作工具赋能内容生产,进而通过平台的互动机制促进用…...
【MFC】07.MFC六大机制:消息映射-笔记
本专栏上两篇文章分别介绍了【MFC】05.MFC第一大机制:程序启动机制和【MFC】06.MFC第二大机制:窗口创建机制,这篇文章来为大家介绍MFC的第三大机制:消息映射 typfd要实现消息映射,必须满足的三个条件: 类必…...
python操作数据库
python操作数据库 首先安装数据插件 pip install pymysqlfrom pymysql import Connection # 引入数据库第三方包# 创建链接 conn Connection(host"localhost", # 主机名ipport3306,user"root",# 用户名password"123456" # 密码 )print(con…...
【C语言】小游戏-三字棋
大家好,我是深鱼~ 目录 一、游戏介绍 二、文件分装 三、代码实现步骤 1.制作简易游戏菜单 2.初始化棋盘 3.打印棋盘 4.玩家下棋 5.电脑随机下棋 6.判断输赢 7.判断棋盘是否满了 四、完整代码 game.h(相关函数的声明,整个代码要引用的头文件以及宏…...
多线程与并发编程面试题总结
多线程与并发编程 多线程 线程和进程的区别? 从操作系统层面上来讲:进程(process)在计算机里有单独的地址空间,而线程只有单独的堆栈和局部内存空间,线程之间是共享地址空间的,正是由于这个特性,对于同…...
在多页面应用和单页面应用中(例如vue)怎么提高seo搜索引擎优化
那么 我们要先知道 搜索引擎是怎么工作的? 搜索引擎是通过一系列步骤来工作的,以下是其基本原理: 1、网络爬虫:搜索引擎使用网络爬虫(也称为蜘蛛、机器人)来从互联网上抓取网页。网络爬虫按照预定义的规则…...
Dubbo 2.7.0 CompletableFuture 异步
了解Java中Future演进历史的同学应该知道,Dubbo 2.6.x及之前版本中使用的Future是在java 5中引入的,所以存在以上一些功能设计上的问题,而在java 8中引入的CompletableFuture进一步丰富了Future接口,很好的解决了这些问题。 Dubb…...
pytest-xdist分布式测试原理浅析
目录 pytest-xdist执行流程: pytest-xdist 模块结构: pytest-xdist分布式测试原理: pytest-xdist源码浅读: pytest-xdist执行流程: 解析命令行参数:pytest-xdist 会解析命令行参数,获取用户…...
研发工程师玩转Kubernetes——PVC通过storageClassName进行延迟绑定
不同的PV可以使用相同的StorageClass,它们是一对多的关系。 PV可以设置节点亲和性。比如下图,local-storage-class-waitforfirstconsumer-pv-ubuntuc只能在节点ubuntuc上;local-storage-class-waitforfirstconsumer-pv-ubuntud只能在节点ubu…...
6.利用matlab完成 符号矩阵的秩和 符号方阵的逆矩阵和行列式 (matlab程序)
1.简述 利用M文件建立矩阵 对于比较大且比较复杂的矩阵,可以为它专门建立一个M文件。下面通过一个简单例子来说明如何利用M文件创建矩阵。 例2-2 利用M文件建立MYMAT矩阵。(1) 启动有关编辑程序或MATLAB文本编辑器,并输入待建矩阵:(2) 把…...
python获取类名__qualname__,解决django接口ObjectDoesNotExist异常寻找model的问题
在django项目中,经常使用类似Model.objects.get(id1)的方法取对象,默认抛出的异常是ObjectDoesNotExist类型,通过try catch可以把异常捕获,获取的异常是Model.DoesNotExist类型, 要获知其类名,可以使用__na…...
电流的测量(分流电流表)
在当今的大多数仪器应用中,可以使用两种常见的电流测量方法:分流电流表方法和反馈电流表方法。分流电流表方法通常与通用数字万用表 (DMM)一起使用,用于测量分流电阻器上的电压测量值。该电压测量结果与已知的电阻值相结合,得出电…...
Leetcode每日一题:23. 合并 K 个升序链表(2023.8.12 C++)
目录 23. 合并 K 个升序链表 题目描述: 实现代码与解析: 优先级队列: 原理思路: 23. 合并 K 个升序链表 题目描述: 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表…...
越南的区块链和NFT市场调研
越南的区块链和NFT市场调研 基本介绍 https://zh.wikipedia.org/wiki/%E8%B6%8A%E5%8D%97 语言文字: 越南语, 文字以国语字(越南罗马字)为主,汉喃文(汉字) 货币:越南盾 人口(2022…...
MySQL常用语句
当涉及到与关系型数据库进行交互时,以下是一些常用的 SQL 语句,可以帮助你进行数据查询、插入、更新和删除等操作: 查询数据: 查询所有数据:SELECT * FROM table_name; 查询特定列数据:SELECT column1, col…...
Mongodb:业务应用(1)
环境搭建参考:mongodb:环境搭建_Success___的博客-CSDN博客 需求: 在文章搜索服务中实现保存搜索记录到mongdb 并在搜索时查询出mongdb保存的数据 1、安装mongodb依赖 <dependency><groupId>org.springframework.data</groupI…...
【vue】vue中按钮权限控制:
文章目录 一、获取权限码二、三种按钮级别的权限控制方式【1】函数方式【2】组件方式【3】指令方式 一、获取权限码 要做权限控制,肯定需要一个code,无论是权限码还是角色码都可以,一般后端会一次性返回,然后全局存储起来就可以了…...
【博客695】k8s subPathExpr作用
k8s subPathExpr作用 场景: 对于一个deployment或者job拉起的服务,所有pod都是一样的配置,如果都挂载了宿主机的同一个目录,那么就会互相干扰,我们希望挂载相同目录,且在这个目录下,每个pod建立…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
高防服务器价格高原因分析
高防服务器的价格较高,主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因: 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器,因此…...
作为点的对象CenterNet论文阅读
摘要 检测器将图像中的物体表示为轴对齐的边界框。大多数成功的目标检测方法都会枚举几乎完整的潜在目标位置列表,并对每一个位置进行分类。这种做法既浪费又低效,并且需要额外的后处理。在本文中,我们采取了不同的方法。我们将物体建模为单…...
Qt学习及使用_第1部分_认识Qt---Qt开发基本流程
前言 学以致用,通过QT框架的学习,一边实践,一边探索编程的方方面面. 参考书:<Qt 6 C开发指南>(以下称"本书") 标识说明:概念用粗体倾斜.重点内容用(加粗黑体)---重点内容(红字)---重点内容(加粗红字), 本书原话内容用深蓝色标识,比较重要的内容用加粗倾…...
【R语言编程——数据调用】
这里写自定义目录标题 可用库及数据集外部数据导入方法查看数据集信息 在R语言中,有多个库支持调用内置数据集或外部数据,包括studentdata等教学或示例数据集。以下是常见的库和方法: 可用库及数据集 openintro库 该库包含多个教学数据集&a…...
Linux【5】-----编译和烧写Linux系统镜像(RK3568)
参考:讯为 1、文件系统 不同的文件系统组成了:debian、ubuntu、buildroot、qt等系统 每个文件系统的uboot和kernel是一样的 2、源码目录介绍 目录 3、正式编译 编译脚本build.sh 帮助内容如下: Available options: uboot …...
