【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详解

qt QPalette详解

1、概述 QPalette是Qt框架中用于管理颜色组和角色的一种机制。它允许开发者为应用程序中的不同组件&#xff08;如窗口、按钮、文本框等&#xff09;定义一套统一的颜色方案。QPalette通过定义颜色角色&#xff08;如背景色、前景色、选择色等&#xff09;和颜色组&#xff08…
阅读更多...
Java基本语法和基础数据类型——针对实习面试

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: 取消请求、读取流、获取下载进度...

引言 Fetch API 提供了一个获取资源的接口(包括跨网络通信)。对于任何使用过 XMLHttpRequest 的开发者来说, 对于 Fetch 应该都能轻松上手, 而且新的 API 提供了更强大和灵活的功能集… 本文主要就是记录下, 在使用 Fetch 期间可能会碰到的几个小案例… 一、取消请求 在前端…
阅读更多...
【 纷享销客-注册安全分析报告-无验证方式导致安全隐患】

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

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

mobaxterm 中文输入问号解决办法

无论是终端&#xff0c;还是session的name&#xff0c;输入中文都是问号&#xff0c;那么使用以下方法可解决问题 语言设置中找到英文键盘删除即可
阅读更多...
Hive的数据存储格式

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的核心优势及其应用详解

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

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高可用

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

黑马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用户态文件系统

什么是FUSE用户态文件系统

零. 文件系统 1. 为什么要有文件系统 文件系统是操作系统中管理文件和目录的一种机制。它提供了组织、存储、检索和更新文件的方法&#xff0c;主要如下&#xff1a; 数据组织&#xff1a;文件系统将数据组织成文件和目录&#xff0c;使用户能够更方便地管理和查找文件。每个…
阅读更多...
品牌怎么找到用户发的优质内容，进行加热、复制？

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

在&#xff0c;相对传统媒体来说&#xff0c;社交媒体营销具有更高的成本效益。品牌可以通过相对较低的成本达到大量潜在客户&#xff0c;尤其是通过口碑营销和内容分享&#xff0c;可以实现倍增的传播效果。在社媒营销的过程中&#xff0c;去找到与品牌有关的优质、正向内容&a…
阅读更多...
梁山派入门指南3——串口使用详解，包括串口发送数据、重定向、中断接收不定长数据、DMA+串口接收不定长数据，以及对应的bsp文件和使用示例

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

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

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设置请求里带动态token，看看这两种方法！

问题描述 在使用postman调试接口时&#xff0c;遇到一些需要在请求里加上token的接口&#xff0c;若token出现变化&#xff0c;需要手动修改接口的token值&#xff0c;带来重复的工作量&#xff0c;翻看postman使用手册后&#xff0c;我发现了两种方法可以解决这个问题。 01 …
阅读更多...
商家如何在高德地图上申请店铺入驻？

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

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

Copyright @ 2022~2023