当前位置: 首页 > news >正文

C++笔记---位图

1. 位图的概念

位图(Bitmap)是一种基于位操作的数据结构,用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组,每个元素对应一个二进制位,若该元素存在,则对应的位为1;若不存在,则为0。位图的这种表示方式使得它能够在存储上以极高的空间效率来管理大规模数据。位图特别适用于需要频繁查询和更新的场景,如数据库索引、图像处理和网络协议等。

简单来说,就是一个采用直接定址法的哈希表,只不过一个bit位映射一个数。

底层通常是一个存储整形的数组或vector,将其中的整形数据连起来看作一个存储bit位的数组。下标为n的bit位为1代表n存在,为0代表n不存在。

这样一来,位图存储一个数据的消耗仅为一个bit位,相比于红黑树和哈希表,在对大量的整形数据的进行增删查改时,位图的优势就十分明显了。

优点:增删查改效率极高,空间复杂度低。

缺点:只适用于整型。

2. 位图的实现

STL的 "bitset" 就是位图,其有三个主要接口:set(插入),reset(删除),test(查找)。

bitset - C++ Reference

位图的实现比较简单,就不过多介绍了。

namespace lbz
{template<size_t N>class bitset{public:bitset():_bs(N / 32 + 1, 0){}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= ~(1 << j);}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}private:vector<int> _bs;};

 注意,这里无需在意大小端的问题,因为bit 位的下标只是假想的下标。

我们只需要算出代表x的bit位是哪一个整形中的第几个,并保证各个接口采用相同的逻辑查找即可。

3. 位图的应用

3.1 检查数据是否存在

eg:给40亿个不重复的无符号整数,没排过序。如何判断某个无符号数是否在这40亿个数中?(腾讯、百度等公司出过的面试题)。

思路1:暴力遍历--->时间复杂度O(N),太慢

思路2:排序+二分查找--->时间复杂度O(N * logN) + O(logN),排序消耗大,但是排好序之后可以进行多次查找。

但是上面两种思路都存在着一个问题,那就是需要将40亿个整数存到内存中。

40亿个整数约等于16GB,考虑到电脑中的其他进程,开出这么大的一个数组显然是不现实的。

这时候就可以使用位图来解决,位图中开辟 "UINT_MAX" 个字节(数据范围为0~UINT_MAX),并将数据存储到位图中。此时,数据对内存的占用就可以降低到500MB左右,且查找效率为O(1)

3.2 计算数据个数

eg:给100亿个不重复的无符号整数,没排过序。如何找出出现次数小于2的数据?

一个bit位只能判断存不存在,如果要计数,就只能用多个比特位来映射一个数。

这里,我们可以采用包装多个位图的方式来实现,第一个位图存储第一个bit位,第二个位图存储第二个bit位,以此类推。

template<size_t N>
class two_bitset
{
public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2)// 00 + 1{_bs2.set(x);}else if (!bit1 && bit2)// 01 + 1{_bs1.set(x);_bs2.reset(x);}else if (bit1 && !bit2)// 10 + 1{_bs2.set(x);}}void reset(size_t x){_bs1.reset(x);_bs2.reset(x);}int test(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2)// 00{return 0;}else if (!bit1 && bit2)// 01{return 1;}else if (bit1 && !bit2)// 10{return 2;}else{return 3;}}
private:bitset<N> _bs1;bitset<N> _bs2;
};

先简单介绍一下,之后可能更新。

相关文章:

C++笔记---位图

1. 位图的概念 位图&#xff08;Bitmap&#xff09;是一种基于位操作的数据结构&#xff0c;用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组&#xff0c;每个元素对应一个二进制位&#xff0c;若该元素存在&#xff0c;则对应的位为1&#xff1b;若不存在&#xff…...

ABC370

## A - Raise Both Hands &#xff08;模拟&#xff09; 题意&#xff1a;输入l&#xff0c;r&#xff0c;如果l1r0输出yes&#xff0c;l0r1输出no&#xff0c;否则输出Invalid 代码&#xff1a; #include<bits/stdc.h> using namespace std; typedef long long ll; vo…...

C语言[求x的y次方]

C语言——求x的y次方 这段 C 代码的目的是从用户输入获取两个整数 x 和 y &#xff0c;然后计算 x 的 y 次幂&#xff08;不过这里有个小错误&#xff0c;实际计算的是 x 的 (y - 1) 次幂&#xff0c;后面会详细说&#xff09;&#xff0c;最后输出结果。 代码如下: #include…...

JavaScript part2

一.前言 前面我们讲了一下js的基础语法&#xff0c;但是这些还是远远不够的&#xff0c;我们要想操作标签&#xff0c;实现一个动态且好看的页面&#xff0c;就得学会BOM和DOM&#xff0c;这些都是浏览器和页面的&#xff0c;这样我们才能实现一个好看的页面 二.BOM对象 BOM…...

HarmonyOS开发 - 本地持久化之实现LocalStorage实例

用户首选项为应用提供Key-Value键值型的数据处理能力&#xff0c;支持应用持久化轻量级数据&#xff0c;并对其修改和查询。数据存储形式为键值对&#xff0c;键的类型为字符串型&#xff0c;值的存储数据类型包括数字型、字符型、布尔型以及这3种类型的数组类型。 说明&#x…...

【C++打怪之路Lv12】-- 模板进阶

#1024程序员节&#xff5c;征文# &#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;重生之我在学Linux&#xff0c;C打怪之路&#xff0c;python从入门到精通&#xff0c;数据结构&#xff0c;C语言&#xff0c;C语言题集&#x1f448; 希望得到您…...

第23周Java主流框架入门-SpringMVC 2.RESTful开发风格

课程笔记&#xff1a;RESTful 开发风格 课程介绍 本节课程介绍 RESTful 开发风格&#xff0c;以及如何在 Spring MVC 中应用这种开发模式。传统 MVC 开发通过 Servlet、JSP 和 Java Bean 实现前后端交互&#xff0c;而 RESTful 开发提供了一种新的理念&#xff0c;更适合现代…...

QT枚举类型转字符串和使用QDebug<<重载输出私有枚举类型

一 将QT自带的枚举类型转换为QString 需要的头文件&#xff1a; #include <QMetaObject> #include <QMetaEnum> 测试代码 const QMetaObject *metaObject &QImage::staticMetaObject;QMetaEnum metaEnum metaObject->enumerator(metaObject->indexOf…...

手机柔性屏全贴合视觉应用

在高科技日新月异的今天&#xff0c;手机柔性显示屏作为智能手机市场的新宠&#xff0c;以其独特的可弯曲、轻薄及高耐用性特性引领着行业潮流。然而&#xff0c;在利用贴合机加工这些先进显示屏的过程中&#xff0c;仍面临着诸多技术挑战。其中&#xff0c;高精度对位、应力控…...

《Python游戏编程入门》注-第3章3

《Python游戏编程入门》的“3.2.4 Mad Lib”中介绍了一个名为“Mad Lib”游戏的编写方法。 1 游戏玩法 “Mad Lib”游戏由玩家根据提示输入一些信息&#xff0c;例如男人姓名、女人姓名、喜欢的食物以及太空船的名字等。游戏根据玩家输入的信息编写出一个故事&#xff0c;如图…...

Netty-TCP服务端粘包、拆包问题(两种格式)

前言 最近公司搞了个小业务&#xff0c;需要使用TCP协议&#xff0c;我这边负责服务端。客户端是某个设备&#xff0c;客户端传参格式、包头包尾等都是固定的&#xff0c;不可改变&#xff0c;而且还有个蓝牙传感器&#xff0c;透传数据到这个设备&#xff0c;然后通过这个设备…...

centos安装指定版本的jenkins

打开jenkins镜像包官网&#xff0c;找到自己想要安装的版本&#xff0c;官网地址&#xff1a;https://mirrors.tuna.tsinghua.edu.cn/jenkins/redhat-stable 下载指定版本安装包&#xff1a; wget https://mirrors.tuna.tsinghua.edu.cn/jenkins/redhat-stable/jenkins-2.452.…...

QT 周期性的杀死一个进程(软件),一分钟后自动退出

1.原因&#xff1a;某软件开机自启动很烦&#xff0c;搞一个程序干掉这个自启动的软件 2.QT代码 main.cpp #include "KillXXX.h" #include <QtWidgets/QApplication>int main(int argc, char *argv[]) {QApplication a(argc, argv);KillXXX k;return a.exec…...

MySQL任意版本安装卸载和数据库原理图绘制

MYSQL任意版本安装和卸载 安装&#xff1a; 1、解压文件 --- 不能出现中文路径 2、在解压目录&#xff08;安装目录&#xff09;下&#xff1a; 1>.创建data文件夹 2>.创建配置文件my.txt 然后修改成ini格式 3、修改配置文件 basedirD:\\mysql\\mysql-5.7.28-winx64…...

技术成神之路:设计模式(二十三)解释器模式

相关文章&#xff1a;技术成神之路&#xff1a;二十三种设计模式(导航页) 介绍 解释器模式&#xff08;Interpreter Pattern&#xff09;是一种行为设计模式&#xff0c;用于定义一种语言的文法表示&#xff0c;并提供一个解释器来处理这种文法。它用于处理具有特定语法或表达…...

2024软考《软件设计师》-Python专题知识(含历年真题解析)

自2020年之后&#xff0c;软考软件设计师考试在综合知识部分开始增加Python编程语言相关考点&#xff0c;每年会考2~3分的样子。本文将结合近几年常考的内容&#xff0c;扩展一下Pyhton的基础知识&#xff01;考前看一看&#xff0c;或许有所帮助。 一、基础语法 标识符 第一…...

基于大数据 Python+Vue 旅游推荐可视化系统(源码+LW+部署讲解+数据库+ppt)

&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 会持续一直更新下去 有问必答 一键收藏关注不迷路 源码获取&#xff1a;https://pan.baidu.com/s/1aRpOv3f2sdtVYOogQjb8jg?pwdjf1d 提取码: jf1d &#…...

使用虚拟机搭建环境:CentOS7 Docker、MySQL、Redis 安装与配置

创作灵感 项目实践总结&#xff1a;记录了在虚拟机中安装与配置CentOS7环境下的Docker、MySQL、Redis的全过程&#xff0c;帮助理解和应用各项技术。技术笔记与问题总结&#xff1a;详细梳理了每一步安装的关键点与常见问题&#xff0c;并给出了解决方案。职业感悟与心得&…...

[分享] Docker容器可视化管理工具 - WGCLOUD

WGCLOUD是新一代运维监测平台&#xff0c;它可以监控Docker容器的各种性能数据&#xff0c;比如内存&#xff0c;cpu&#xff0c;Image&#xff0c;运行时间&#xff0c;运行状态&#xff0c;端口映射等信息 WGCLOUD也支持在页面启动&#xff0c;重启&#xff0c;停止Docker容…...

保存网页中 canvas 的内容

在开发人员工具中,保存网页中 canvas 的内容,可以用这个方法: 1. 在 dom 中创建一个下载按钮 <button id="save">保存</button>2. 控制台中运行: const gCanvas = document.querySelector(#page_1);function onSave() {gCanvas.toBlob((blob) =&g…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...