【C++】位图详解(一文彻底搞懂位图的使用方法与底层原理)

目录

1.位图的概念

2.位图的使用方法

定义与创建

设置和清除

位访问和检查

转换为其他格式

3.位图的使用场景

1.快速的查找某个数据是否在一个集合中

2.排序+去重

3.求两个集合的交集和并集

4.位图的底层实现

私有成员定义与初始化

set和reset的实现


前面的博客我们介绍了哈希结构以及以哈希为底层结构的容器unordered_map和unordered_set,相较于以红黑树为底层的map和set,它们的优势是更高效的查找(平均为O(1))不过代价是更多内存的消耗,这些内存的消耗在某些场景下会变得致命:

这是一道腾讯的面试题:

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

既然是追求高效的查询,显然哈希结构更具优势,但是在这里如果使用哈希表,会占用大量的内存。40亿个整数键需要16GB的内存,为了解决哈希冲突,实际所需容量会更多(1.5倍以上)。这是什么概念呢?

这是博主的笔记本规格,可以看到RAM(运行内存)刚好是16GB(加上虚拟内存也不过20GB左右),也就是说即使我“倾家荡产”也不足以实现上述操作

用其他办法(比如压缩数据结构)的确可以节省内存的占用,但是并无法达到快速查询的效果。现在存在如下矛盾:

①:更快查询效率的需要

②:更少内存占用的需要

我们需要寻找一种办法,同时满足上述两种需求,以解决这个问题。于是乎,位图闪亮登场~

1.位图的概念

所谓位图,是一种使用二进制位(bit位)来表示数据状态的数据结构。其每一个二进制位(bit)可以表示一个数据的存在与否,从而通过极少的内存实现大规模数据的存储与处理。

比如,存储1个整形需要4个字节的空间,现在我用存储1个整形的空间,就可以表示32个整形元素的存储状态:

1个整形有32个bit位,每一位都可以表示一个数据的状态(数据1存在就让第一位bit值变成1),因此我们可以把每一个比特位都看成一个bool值,bool值为1表示数据存在,为0表示不存在

现在我们回到上面那道问题:

原本需要16GB的空间存储40亿个整数,而1个整形的空间可以表示32个数据的存在状态,所以现在只需要 16GB/32 = 512KB 的存储空间,而且由于数据是映射存储的,我们想知道 整数x 存不存在,只需要看第 x 个比特位是否为1即可,所以查询的时间复杂度是O(1)。这种映射关系和哈希结构很像,所以位图实际上就是哈希的一种应用。

总结:位图是如何查询到数据的

位图只存储数据的状态(即是否存在),而不存储数据本身的值,但是我们仍可以根据位图的位索引位置间接查询到数据本身。比如要记录整数 5 是否存在,则位图第 5 位会被置为 1,看到第 5 位是 1,可以知道 5 存在,但位图中并没有存储“5”的数值。总之,我们并不是根据数据本身进行查询,而是通过位置映射关系进行查询

 

2.位图的使用方法

C++标准库提供了一个名为 bitset 的数据结构,用于管理和操作bit数组,可用于实现位图。

以下是bitset使用方法的介绍:

定义与创建

bitset 是一个模版类,模版参数表示位数,在编译时确定大小,例如:

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

int main()
{
	bitset<8> bits;             // 定义一个大小为 8 位的位图(位数组)
	bitset<16> bits16(0xF0F0);  // 定义一个大小为 16 位的位图,并初始化为二进制 1111 0000 1111 0000
	bitset<8> bitsFromStr("10101010"); // 从字符串创建一个 8 位位图

	return 0;
}

设置和清除

bitset 提供了很多方法用于位操作和状态管理:

set()将所有位设置为 1
set(size_t pos, bool value = true)将指定位置 pos 的位设置为 value
reset()将所有位重置为 0
reset(size_t pos)将指定位置 pos 的位重置为 0
flip()将所有位翻转(0 变 1,1 变 0)
flip(size_t pos)将指定位置 pos 的位翻转

 

 

 

 

 

 

 

	bitset<8> bits("10101010");
	bits.set(0);        // 将第 0 位设置为 1,结果为 10101011
	bits.reset(1);      // 将第 1 位设置为 0,结果为 10101001
	bits.flip();        // 翻转所有位,结果为 01010110
	bits.flip(2);       // 翻转第 2 位,结果为 01010010

 

位访问和检查

operator[]使用 [] 访问位
test(size_t pos)测试指定位置的位是否为 1,返回 true 表示为 1,返回 false 表示为 0
all()检查所有位是否都为 1,是返回 true,否则返回 false
any()检查是否存在至少一位为 1,是则返回 true
none()检查是否所有位都是 0,是则返回 true
count()返回所有 1 的数量

 

转换为其他格式

to_string()将位图转换为字符串
to_ulong()将位图转换为 unsigned long 类型
to_ullong()将位图转换为 unsigned long long 类型

3.位图的使用场景

1.快速的查找某个数据是否在一个集合中

现在随机生成10000个范围在0~15000的整数,检验某些数据是否存在:

#include <bitset>
#include <iostream>
#include <vector>
#include <random>
#include <chrono>

using namespace std;

int main() {
    const int num_elements = 10000; // 元素数量
    const int min_value = 0;         // 最小值
    const int max_value = 15000;     // 最大值

    // 获取当前时间作为种子
    unsigned seed = static_cast<unsigned>(std::chrono::system_clock::now().time_since_epoch().count());
    std::mt19937 gen(seed); // 使用当前时间作为种子生成随机数

    std::uniform_int_distribution<> dis(min_value, max_value); // 均匀分布

    // 创建一个 vector 并填充随机数
    std::vector<int> nums(num_elements);
    for (int& number : nums) {
        number = dis(gen); // 生成随机数并赋值
    }

    // 创建位图,范围是 0 到 max_value
    bitset<max_value + 1> bitset;

    // 将生成的随机数映射到位图中
    for (const auto& it : nums) {
        bitset.set(it);
    }

    // 检查某个数是否存在
    vector<int> num_test = { 5, 64, 862, 1356, 45, 236, 856, 12, 489, 6116, 1648, 216, 1554, 335, 795, 211 };
    cout << "存在性检查结果:\n";
    for (const auto& it : num_test) {
        if (bitset.test(it)) {  // 检查 num 的位是否为 1
            cout << it << " 存在.\n";
        }
        else {
            cout << it << " 不存在.\n";
        }
    }

    return 0;
}

分别运行三次的结果: 

2.排序+去重

位图和哈希表底层都是哈希结构,为什么哈希表不能实现排序而位图可以呢?

因为哈希表的存储位置是通过哈希函数求得的的哈希值决定的,不同的元素可能有相同的哈希值,因此元素的存储是非线性的。

位图的存储位置就是数据本身决定的,每个比特位对于一个元素,因此元素的存储是线性的。

下面来看示例:

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

const size_t MAX_SIZE = 1000;  // 数据范围是 0 到 1,000,000

int main() {
    bitset<MAX_SIZE> bitset;

    // 模拟数据插入(包括重复数据)
    vector<int> data = { 566,254,4,26,326,2,495,56,98,26,254,566,235,66 };
    cout << "排序+去重前的数据:\n";
    for (auto it : data) {
        cout << it << " ";
    }
    cout << "\n";

    for (int num : data) {
        bitset.set(num);  // 将数据映射到位图中
    }

    // 遍历位图,输出所有置位为 1 的位置(即有序的、去重的数据)
    cout << "排序+去重后的数据:\n";
    for (size_t i = 0; i < MAX_SIZE; ++i) {
        if (bitset.test(i)) {
            cout << i << " ";
        }
    }
    cout << "\n";

    return 0;
}

 

3.求两个集合的交集和并集

位图是如何完成交集并集运算的呢?由于位图的每一个bit位存储对应元素的bool值(0或1),而相同元素在不同位图中的存储位置是一样的,我们对两个位图进行按位与运算,就可以得到交集;进行按位或运算,就可以得到并集。

#include <iostream>
#include <bitset>
const size_t MAX_SIZE = 1000000;
using namespace std;

int main() {
    bitset<MAX_SIZE> setA;
    bitset<MAX_SIZE> setB;

    // 插入一些数据到集合 A
    setA.set(123456);
    setA.set(654321);
    setA.set(500);

    // 插入一些数据到集合 B
    setB.set(654321);
    setB.set(500);
    setB.set(999999);

    // 求交集(A & B)
    bitset<MAX_SIZE> intersection = setA & setB;
    cout << "交集:\n";
    for (size_t i = 0; i < MAX_SIZE; ++i) {
        if (intersection.test(i)) {
            cout << i << " ";
        }
    }
    cout << "\n";

    // 求并集(A | B)
    bitset<MAX_SIZE> unionSet = setA | setB;
    cout << "并集:\n";
    for (size_t i = 0; i < MAX_SIZE; ++i) {
        if (unionSet.test(i)) {
            cout << i << " ";
        }
    }
    cout << "\n";

    return 0;
}

4.位图的底层实现

位图的底层其实是一个vector容器,容器内部存放整形元素,一个整形元素可以存放32个对应元素的状态(bool值),并且通过位运算实现映射关系的对应

底层存储结构:

私有成员定义与初始化

在bitset类中,我们需要一个_bitCount成员表示比特位的总个数用于对bitset的初始化,以及一个_bit(vector<int>类型的容器 )用于存储元素。

class bitset
{

private:
	vector<int> _bit;
	size_t _bitCount;
};

位图的大小是固定的,根据_bitCount的大小进行空间开辟,而_bitCount的大小是由待存储元素的最大值决定的。但是_bitCount的单位是bit,而vector中存储单位是整形,所以我们需要进行换算,_bitCount>>5(也就是除以2^5)并+1(由于除法会向下取整,例如 bitCount 是 33,33 >> 5 计算结果是 1,但我们实际上需要 2 个整型来存储 33 个比特位)

	bitset(size_t bitCount)
		: _bit((bitCount >> 5) + 1), _bitCount(bitCount)
	{}

set和reset的实现

假设用which表示要存储的元素,我们需要求得映射位置。我们可以把每个元素当成一个数组,数组中包含32个比特位,此时将which/32就可以得出存储在第几个数组中,并用which%32得到在该数组下的具体比特位,假设which = 152:

存储位置为v[4]的第24个比特位:

如此一来就找到了对应的映射关系。下面是代码部分:

	// 将which比特位置1
	void set(size_t which)
	{
		if (which > _bitCount)
			return;
		size_t index = (which >> 5);
		size_t pos = which % 32;
		_bit[index] |= (1 << pos); // 将对应bit位改为1
	}
	// 将which比特位置0
	void reset(size_t which)
	{
		if (which > _bitCount)
			return;
		size_t index = (which >> 5);
		size_t pos = which % 32;
		_bit[index] &= ~(1 << pos); // 将对应bit位改为0
	}
	// 检测位图中which是否为1
	bool test(size_t which)
	{
		if (which > _bitCount)
			return false;
		size_t index = (which >> 5);
		size_t pos = which % 32;
		return _bit[index] & (1 << pos);
	}
	// 获取位图中比特位的总个数
	size_t size()const { return _bitCount; }

以上就是对位图的详细介绍说明,欢迎指正~

码文不易,还请多多关注支持,这是我持续创作的最大动力!

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

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

相关文章

在线教育系统源码开发详解:网校培训平台搭建的核心技术

本篇文章&#xff0c;笔者将详细介绍在线教育系统源码的开发过程&#xff0c;重点聚焦网校培训平台搭建的核心技术&#xff0c;以期为有意从事在线教育行业的开发者提供实用的参考。 一、在线教育系统的构成 前端负责用户的交互体验&#xff0c;后端处理业务逻辑&#xff0c;…

qt QPalette详解

1、概述 QPalette是Qt框架中用于管理颜色组和角色的一种机制。它允许开发者为应用程序中的不同组件&#xff08;如窗口、按钮、文本框等&#xff09;定义一套统一的颜色方案。QPalette通过定义颜色角色&#xff08;如背景色、前景色、选择色等&#xff09;和颜色组&#xff08…

Java基本语法和基础数据类型——针对实习面试

目录 Java基本语法和基础数据类型标识符和关键字有什么区别&#xff1f;Java关键字有哪些&#xff1f;Java基本数据类型有哪些&#xff1f;什么是自动装箱和拆箱&#xff1f;自动装箱&#xff08;Autoboxing&#xff09;自动拆箱&#xff08;Unboxing&#xff09; 自动装箱和拆…

逻辑磁盘管理 附实验:逻辑卷的组成与划分

分区类型&#xff1a; 1、系统引导分区 就是存放系统的引导文件和Linux的内核文件 2、swap分区 交换分区&#xff0c;系统的物理内存不足时&#xff0c;从一些长时间未运行的程序当中释放一部分内存释放出来的保存到swap分区&#xff0c;这些未运行的程序一旦运行还要从swap空…

fetch: 取消请求、读取流、获取下载进度...

引言 Fetch API 提供了一个获取资源的接口(包括跨网络通信)。对于任何使用过 XMLHttpRequest 的开发者来说, 对于 Fetch 应该都能轻松上手, 而且新的 API 提供了更强大和灵活的功能集… 本文主要就是记录下, 在使用 Fetch 期间可能会碰到的几个小案例… 一、取消请求 在前端…

【 纷享销客-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…

mobaxterm 中文输入问号解决办法

无论是终端&#xff0c;还是session的name&#xff0c;输入中文都是问号&#xff0c;那么使用以下方法可解决问题 语言设置中找到英文键盘删除即可

Hive的数据存储格式

目录 一、前言 二、存储格式 2.1、文本格式&#xff08;TextFile&#xff09; 2.1.1、定义与特点 2.1.2、存储与压缩 2. 1.3、使用场景 2.2、行列式文件&#xff08;ORCFile&#xff09; 2.2.1、ORC的结构 2.2.2、ORC的数据类型 2.2.3、ORC的压缩格式 2.2.3、ORC存储…

Spring Boot的核心优势及其应用详解

目录 前言1. Spring Boot的核心优势1.1 启动依赖的集成1.2 自动化配置 2. 内嵌服务器支持2.1 内嵌Tomcat服务器2.2 独立运行与便捷部署 3. 外部配置管理3.1 多环境支持3.2 配置优先级与外部化配置 4. Spring Boot的应用场景4.1 微服务架构4.2 云原生应用 结语 前言 在现代的Ja…

scala---10.30

val、var package com_1030class Person {var name:String"rose"def sum(n1:Int,n2:Int):Int{n1n2} } object Person{def main(args: Array[String]): Unit {//创建person对象var personnew Person()println(person.sum(10,20))//30println(person.name)person.nam…

ubuntu22.04 docker-compose搭建apisix高可用

首先你得先确保每台主机安装了docker和docker-compose 3台主机 没有安装docker和docker-compose的可以看我前两篇博客 可以先克隆仓库 git clone https://github.com/apache/apisix-docker.git 进入example目录 拷贝dashboard配置文件 将all-in-one中apisix-dashboard文件夹拷…

北大计算机考研难度如何?毕业后就业情况怎么样?

C哥专业提供——计软考研院校选择分析专业课备考指南规划 一、总体情况概述 北京大学计算机 2024 届考研整体呈现 “稳中有升” 的态势。在复试分数线方面&#xff0c;无论是学硕&#xff08;本部&#xff09;还是专硕&#xff08;深圳&#xff09;&#xff0c;较 2023 届均有…

黑马JavaWeb-day04

文章目录 mavenmaven 简介maven 安装IDEA集成maven创建maven项目Maven 坐标依赖管理单元测试 Web入门Springboot 入门HTTP协议三层架构分层解耦 I O C & D I IOC\&DI IOC&DI入门 I O C IOC IOC和 D I DI DI详解 maven maven 简介 maven: M a v e n Maven Maven是…

什么是FUSE用户态文件系统

零. 文件系统 1. 为什么要有文件系统 文件系统是操作系统中管理文件和目录的一种机制。它提供了组织、存储、检索和更新文件的方法&#xff0c;主要如下&#xff1a; 数据组织&#xff1a;文件系统将数据组织成文件和目录&#xff0c;使用户能够更方便地管理和查找文件。每个…

品牌怎么找到用户发的优质内容,进行加热、复制?

在&#xff0c;相对传统媒体来说&#xff0c;社交媒体营销具有更高的成本效益。品牌可以通过相对较低的成本达到大量潜在客户&#xff0c;尤其是通过口碑营销和内容分享&#xff0c;可以实现倍增的传播效果。在社媒营销的过程中&#xff0c;去找到与品牌有关的优质、正向内容&a…

梁山派入门指南3——串口使用详解,包括串口发送数据、重定向、中断接收不定长数据、DMA+串口接收不定长数据,以及对应的bsp文件和使用示例

梁山派入门指南3——串口使用详解&#xff0c;包括串口发送数据、重定向、中断接收不定长数据、DMA串口接收不定长数据&#xff0c;以及对应的bsp文件和使用示例 1. 串口发送数据1.1 串口简介1.2 梁山派上的串口开发1.3 bsp_uart文件&#xff08;只发送不接收&#xff0c;兼容串…

notepad++ compare插件的离线下载和安装

一、离线安装 去改地址找到最新的插件&#xff1a;https://github.com/notepad-plus-plus/nppPluginList/blob/master/doc/plugin_list_x64.md下载之后复制到插件文件夹&#xff0c;插件文件夹的打开方式如下 注意目录&#xff1a; 二、问题汇总 &#xff08;1&#xff09…

你的网站需要防护吗?

你的网站经常被恶意爬虫&#xff0c;重要数据被批量搬运吗&#xff1f; 你想知道你的网站是不是安全的&#xff0c;有没有被 xss攻击、sql注入、命令注入等等这些乱七八糟的攻击手段攻击吗&#xff1f; 2014年我还是学生的时候&#xff0c;负责学院官网的维护&#xff0c;一…

在postman设置请求里带动态token,看看这两种方法!

问题描述 在使用postman调试接口时&#xff0c;遇到一些需要在请求里加上token的接口&#xff0c;若token出现变化&#xff0c;需要手动修改接口的token值&#xff0c;带来重复的工作量&#xff0c;翻看postman使用手册后&#xff0c;我发现了两种方法可以解决这个问题。 01 …

商家如何在高德地图上申请店铺入驻?

在当今数字化时代&#xff0c;互联网成为了消费者寻找商品和服务的主要渠道。高德地图作为国内领先的地图导航软件&#xff0c;不仅拥有庞大的用户基础&#xff0c;还为商家提供了优质的店铺展示平台。因此&#xff0c;对于实体店商家而言&#xff0c;入驻高德地图是提升店铺曝…