【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 0000bitset<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，结果为 10101011bits.reset(1);      // 将第 1 位设置为 0，结果为 10101001bits.flip();        // 翻转所有位，结果为 01010110bits.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_valuebitset<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 的位是否为 1cout << 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,000int 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;// 插入一些数据到集合 AsetA.set(123456);setA.set(654321);setA.set(500);// 插入一些数据到集合 BsetB.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比特位置1void 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比特位置0void 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是否为1bool 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; }

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

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

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

补齐：相交链表：扣160

补齐：相交链表：扣160

梦重新开始的地方 – 相交链表 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。图示两个链表在节点 c1 开始相交&#xff1a; 示例&#xff1a; 何解&#xff1f; 暴力&…
阅读更多...
Python：入门基础

Python：入门基础

目录 常量和表达式 变量 变量的语法 变量的类型 动态类型特性 注释的使用 输入和输出 通过控制台输出 通过控制台输入 运算符 算术运算符 关系运算符 逻辑运算符 赋值运算符 常量和表达式 print是Python中的一个内置函数&#xff0c;使用print函数可以将数据打印…
阅读更多...
手动搭建koa+ts项目框架（node开发配置环境变量）

手动搭建koa+ts项目框架（node开发配置环境变量）

文章目录 一、安装所需依赖二、设置package.json三、定义ts &#xff08;可选&#xff09;四、配置环境变量文件五、引入变量文件总结如有启发&#xff0c;可点赞收藏哟~ 一、安装所需依赖 pnpm add dotenv二、设置package.json 先配置脚本设置对应环境变量NODE_ENV {"…
阅读更多...
吞吐量最高飙升20倍！破解强化学习训练部署难题

吞吐量最高飙升20倍！破解强化学习训练部署难题

**强化学习&#xff08;RL&#xff09;对大模型复杂推理能力提升有关键作用&#xff0c;然而&#xff0c;RL 复杂的计算流程以及现有系统局限性&#xff0c;也给训练和部署带来了挑战。近日&#xff0c;字节跳动豆包大模型团队与香港大学联合提出 HybridFlow&#xff08;开源项…
阅读更多...
Unity 插件编译版本.net 4.0

Unity 插件编译版本.net 4.0

项目中用到了Google.ProtocolBuffersLite.dll 这个动态链接库&#xff0c;在升级完Unity版本后出现了 ”Unity targets .NET 4.x and is marked as compatible with editor, Editor can only use assemblies targeting .NET 3.5 or lower“ 的问题。 解决方法&#xff1a; 1、…
阅读更多...
Cpp二叉搜索树的讲解与实现(21)

Cpp二叉搜索树的讲解与实现(21)

文章目录 前言一、二叉搜索树的概念定义特点 二、二叉树的实现基本框架查找插入删除当只有0 ~ 1个孩子的时候当有2个孩子的时候 三、二叉树的应用K模型KV模型 四、二叉树的性能分析总结 前言 这是全新的一个篇章呢&#xff0c;二叉搜索树是我们接下来学习set、map的前提 迈过它…
阅读更多...
Elasticsearch —— ES 环境搭建、概念、基本操作、文档操作、SpringBoot继承ES

Elasticsearch —— ES 环境搭建、概念、基本操作、文档操作、SpringBoot继承ES

文章中会用到的文件&#xff0c;如果官网下不了可以在这下 链接: https://pan.baidu.com/s/1SeRdqLo0E0CmaVJdoZs_nQ?pwdxr76 提取码: xr76 一、 ES 环境搭建 注&#xff1a;环境搭建过程中的命令窗口不能关闭&#xff0c;关闭了服务就会关闭&#xff08;除了修改设置后重启的…
阅读更多...
第八届御网杯线下赛Pwn方向题解

第八届御网杯线下赛Pwn方向题解

由于最近比赛有点多&#xff0c;而且赶上招新&#xff0c;导致原本应该及时总结的比赛搁置了&#xff0c;总结来说还是得多练&#xff0c;因为时间很短像这种线下赛&#xff0c;一般只有几个小时&#xff0c;所以思路一定要清晰&#xff0c;我还是经验太少了&#xff0c;导致比…
阅读更多...
Ethernet 系列（6）-- 基础学习::OSI Model

Ethernet 系列（6）-- 基础学习::OSI Model

&#xff08;写在前面&#xff1a;最近在学习车载以太网的知识&#xff0c;顺便记录一下知识点。&#xff09; OSI&#xff08;Open System Interconnect &#xff09;模型是一种网络通信框架&#xff0c;由国际标准化组织&#xff08;‌ISO&#xff09;在1985年提出&#xff0…
阅读更多...
Java 字符流详解

Java 字符流详解

在 Java 的 I/O 体系中&#xff0c;字符流&#xff08;Reader 和 Writer&#xff09;是专门用于处理文本数据的输入输出流。与字节流不同&#xff0c;字符流以字符为单位进行读取和写入&#xff0c;能够更好地处理文本信息&#xff0c;尤其是包含多字节字符&#xff08;如中文&…
阅读更多...
Linux 多线程编程

Linux 多线程编程

韦东山的例程所谓线程&#xff0c;就是操作系统所能调度的最小单位。普通的进程&#xff0c;只有一个线程在执行对应的逻辑。我们可以通过多线程编程&#xff0c;使一个进程可以去执行多个不同的任务。相比多进程编程而言&#xff0c;线程享有共享资源&#xff0c;即在进程中出…
阅读更多...
后端：Spring-1

后端：Spring-1

文章目录 1. 了解 spring(Spring Framework)2. 基于maven搭建Spring框架2.1 纯xml配置方式来实现Spring2.2 注解方式来实现Spring3. Java Config类来实现Spring 2.4 总结 1. 了解 spring(Spring Framework) 传统方式构建spring(指的是Spring Framework)项目&#xff0c;导入依…
阅读更多...
【C++动态规划 01背包】2787. 将一个数字表示成幂的和的方案数

【C++动态规划 01背包】2787. 将一个数字表示成幂的和的方案数

本文涉及知识点 C动态规划 C背包问题 LeetCode2787. 将一个数字表示成幂的和的方案数 给你两个 正 整数 n 和 x 。 请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说&#xff0c;你需要返回互不相同整数 [n1, n2, …, nk] 的集合数目&#xff0c;满…
阅读更多...
Python爬虫的京东大冒险：如何高效获取商品详情的秘籍

Python爬虫的京东大冒险：如何高效获取商品详情的秘籍

在这个由代码编织的电商世界里&#xff0c;京东商品详情就像是被锁在高塔中的公主&#xff0c;等待着勇敢的Python爬虫骑士去解救。今天&#xff0c;我们要讲述的是如何成为一名Python爬虫骑士&#xff0c;携带你的代码长矛&#xff0c;穿梭在API的数据森林中&#xff0c;高效获…
阅读更多...
SpringBoot【实用篇】- 测试

SpringBoot【实用篇】- 测试

文章目录 目标&#xff1a;1.加载测试专用属性3.Web环境模拟测试2.加载测试专用配置4.数据层测试回滚5.测试用例数据设定 目标&#xff1a; 加载测试专用属性加载测试专用配置Web环境模拟测试数据层测试回滚测试用例数据设定 1.加载测试专用属性 我们在前面讲配置高级的时候…
阅读更多...
vfx特效有多烧钱？云渲染农场减少vfx特效成本

vfx特效有多烧钱？云渲染农场减少vfx特效成本

特效制作一直是电影制作中的烧钱大户&#xff0c;尤其是视觉特效&#xff08;VFX&#xff09;的高昂成本让许多项目望而却步。但随着云渲染农场技术的发展&#xff0c;VFX特效的成本得到了有效控制&#xff0c;为电影工业带来了革命性的变化。 在电影工业中&#xff0c;VFX特效…
阅读更多...
任何python安装gdal出现的问题

任何python安装gdal出现的问题

Releases cgohlke/geospatial-wheels GitHubGeospatial library wheels for Python on Windows. Contribute to cgohlke/geospatial-wheels development by creating an account on GitHub.https://github.com/cgohlke/geospatial-wheels/releases 各种乱七八糟的gdal库问题…
阅读更多...
tensorflow案例4--人脸识别(损失函数选取，调用VGG16模型以及改进写法)

tensorflow案例4--人脸识别(损失函数选取，调用VGG16模型以及改进写法)

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 前言 这个模型结构算上之前的pytorch版本的&#xff0c;算是花了不少时间&#xff0c;但是效果一直没有达到理想情况&#xff0c;主要是验证集和训练集准确率…
阅读更多...
SPA和SSR

SPA和SSR

单页面应用程序(SPA) 单页面应用(SPA)全称是:Single-page application, SPA应用是在客户端呈现的(术语称:CRS)。 SPA应用默认只返回一个空HTML页面&#xff0c;如:body只有<div id"app"></div>而整个应用程序的内容都是通过JavaScript动态加载&#xf…
阅读更多...
【 纷享销客-注册安全分析报告-无验证方式导致安全隐患】

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

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

Copyright @ 2022~2023