＜C++＞ STL_bitset使用和模拟实现

bitset的介绍

位图的引入

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

要判断一个数是否在某一堆数中，我们可能会想到如下方法：

  • 将这一堆数进行排序，然后通过二分查找的方法判断该数是否在这一堆数中。
  • 将这一堆数插入到unordered_set容器中，然后调用find函数判断该数是否在这一堆数中。

单从方法上来看，这两种方法都是可以，而且效率也不错，第一种方法的时间复杂度是O(N*LogN)，第二种方法的时间复杂度是O(N)。

但问题是这里有40亿个数，若是我们要将这些数全部加载到内存当中，那么将会占用16G的空间，空间消耗是很大的。因此从空间消耗来看，上面这两种方法实际都是不可行的。

位图解决

实际在这个问题当中，我们只需要判断一个数在或是不在，即只有两种状态，那么我们可以用一个比特位来表示数据是否存在，如果比特位为1则表示存在，比特位为0则表示不存在。比如：

在这里插入图片描述

无符号整数总共有2的32次方个，因此记录这些数字就需要2的32次方个比特位，也就是512M的内存空间，内存消耗大大减少。

位图的概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

位图的应用

常见位图的应用如下：

  1. 快速查找某个数据是否在一个集合中。
  2. 排序。
  3. 求两个集合的交集、并集等。
  4. 操作系统中磁盘块标记。
  5. 内核中信号标志位（信号屏蔽字和未决信号集）。

bitset的使用

bitset是一种特殊的容器类，它的每个元素只占用一位，只能为0或1。

bitset的定义方式

创建bitset对象，你可以直接指定它的大小，或者使用一个无符号长整型数或字符串初始化它：

方式一： 构造一个16位的位图，所有位都初始化为0。

bitset<16> bs1; //0000000000000000

方式二： 构造一个16位的位图，根据所给值初始化位图的前n位。

bitset<16> bs2(0xfa5); //0000111110100101

方式三： 构造一个16位的位图，根据字符串中的0/1序列初始化位图的前n位。

bitset<16> bs3(string("10111001")); //0000000010111001

bitset成员函数的使用

bitset类提供了以下一些常用的成员函数：

  • set：将bitset中的一位或所有位设置为1
  • reset：将bitset中的一位或所有位设置为0
  • flip：翻转bitset中的一位或所有位
  • test：获取指定位的状态
  • count：返回bitset中1的个数
  • size：返回bitset中位的个数
  • any：如果bitset中至少有一位为1，则返回true
  • none：如果bitset中所有位都为0，则返回true
  • all：如果所有位都被设置，则返回true
  • to_string：将bitset转换为字符串
  • to_ulong 或 to_ullong：将bitset转换为无符号(长)整型数

使用示例：

#include <bitset>
#include <iostream>
using namespace std;int main() {bitset<8> bs;//位置从0开始bs.set(2);         //设置第2位bs.set(4);         //设置第4位cout << bs << endl;//00010100bs.flip();                 //反转所有位cout << bs << endl;        //11101011cout << bs.count() << endl;//6cout << bs.test(3) << endl;//1  3的位置为1bs.reset(0);       //清空第0位,第0位变成了0cout << bs << endl;//11101010bs.flip(7);        //反转第7位cout << bs << endl;//01101010cout << bs.size() << endl;//8cout << bs.any() << endl;//任何位为1，就返回true 1bs.reset();               //清空所有位cout << bs.none() << endl;//没有位被设置，就返回true 1bs.set();                //设置所有位cout << bs.all() << endl;//所有位被设置，返回true  1return 0;
}22211

注意： 使用成员函数set、reset、flip时，若指定了某一位则操作该位，若未指定位则操作所有位。

bitset运算符的使用

一、bitset中>>、<<运算符的使用。
bitset容器对>>、<<运算符进行了重载，我们可以直接使用>>、<<运算符对biset容器定义出来的对象进行输入输出操作。

#include <iostream>
#include <bitset>
using namespace std;int main() {bitset<8> bs;cin >> bs;         //10110cout << bs << endl;//00010110return 0;
}

二、bitset中赋值运算符、关系运算符、复合赋值运算符、单目运算符的使用。

bitset容器中不仅对赋值运算符和一些关系运算符进行了重载，而且对一些复合赋值运算符和单目运算符也进行了重载，我们可以直接使用这些运算符对各个位图进行操作。

包括如下运算符：

  • 赋值运算符：=。
  • 关系运算符：==、!=。
  • 复合赋值运算符：&=、|=、^=、<<=、>>=。
  • 单目运算符：~。

三、bitset中位运算符的使用。
bitset容器中同时也对三个位运算符进行了重载，我们可以直接使用&、|、^对各个位图进行操作。

#include <bitset>
#include <iostream>
#include <string>
using namespace std;int main() {bitset<8> bs1(string("10101010"));bitset<8> bs2(string("01010101"));cout << (bs1 & bs2) << endl;//00000000cout << (bs1 | bs2) << endl;//11111111cout << (bs1 ^ bs2) << endl;//11111111return 0;
}

四、bitset中[ ]运算符的使用。
bitset容器中对[ ]运算符进行了重载，我们可以直接使用[ ]对指定位进行访问或修改。

#include <bitset>
#include <iostream>
#include <string>
using namespace std;int main() {bitset<8> bs(string("00110101"));cout << bs[0] << endl;//1bs[0] = 0;cout << bs << endl;//00110100return 0;
}

bitset的模拟实现

bit类各函数接口总览

namespace cl {//模拟实现位图template<size_t N>class bitset {public://构造函数bitset();//设置位void set(size_t pos);//清空位void reset(size_t pos);//反转位void flip(size_t pos);//获取位的状态bool test(size_t pos);//获取可以容纳的位的个数size_t size();//获取被设置位的个数size_t count();//判断位图中是否有位被设置bool any();//判断位图中是否全部位都没有被设置bool none();//判断位图中是否全部位都被设置bool all();//打印函数void Print();private:vector<int> _bits;//位图};
}// namespace cl

bitset类的实现

构造函数

在构造位图时，我们需要根据所给位数N，创建一个N位的位图，并且将该位图中的所有位都初始化为0。

一个整型有32个比特位，因此N个位的位图就需要用到N/32个整型，但是实际我们所需的整型个数是N/32+1，因为所给非类型模板参数N的值可能并不是32的整数倍。

例如，当N为40时，我们需要用到两个整型，即40/32+1=2。

在这里插入图片描述

代码如下：

//构造函数
bitset(){_bits.resize(N / 32 + 1, 0);
}

成员函数

set

set成员函数用于设置位。

设置位图中指定的位的方法如下：

  1. 计算出该位位于第 i 个整数的第 j 个比特位。

  2. 将1左移 j 位后与第 i 个整数进行或运算即可。

    在这里插入图片描述

代码如下：

//设置位
void set(size_t pos){assert(pos < N);//算出pos映射的位在第i个整数的第j个位int i = pos / 32;int j = pos % 32;_bits[i] |= (1 << j); //将该位设置为1（不影响其他位）
}
reset

reset成员函数用于清空位。

清空位图中指定的位的方法如下：

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。

在这里插入图片描述

代码如下：

//清空位
void reset(size_t pos){assert(pos < N);//算出pos映射的位在第i个整数的第j个位int i = pos / 32;int j = pos % 32;_bits[i] &= (~(1 << j)); //将该位设置为0（不影响其他位）1进行翻转后只有第j位置位0 其他都是1，所以只会影响第j位置的数字
}
flip

flip成员函数用于反转位。

反转位图中指定的位的方法如下：

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位后与第 i 个整数进行异或运算即可。

在这里插入图片描述

代码如下：

//反转位
void flip(size_t pos){assert(pos < N);//算出pos映射的位在第i个整数的第j个位int i = pos / 32;int j = pos % 32;_bits[i] ^= (1 << j); //将该进行反转（不影响其他位）
}
test

test成员函数用于获取位的状态。

获取位图中指定的位的状态的方法如下：

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位后与第 i 个整数进行与运算得出结果。
  3. 若结果非0，则该位被设置，否则该位未被设置。

在这里插入图片描述

代码如下：

//获取位的状态
bool test(size_t pos){assert(pos < N);//算出pos映射的位在第i个整数的第j个位int i = pos / 32;int j = pos % 32;//该比特位被设置if (_bits[i] & (1 << j)){return true;} else {//该比特位未被设置return false;} 
}
size、count

size成员函数用于获取位图中可以容纳的位的个数。

我们直接将所给非类型模板参数进行返回即可。

//获取可以容纳的位的个数
size_t size(){return N;
}

count成员函数用于获取位图中被设置的位的个数。

获取位图中被设置的位的个数，也就是统计位图中1的个数，我们只需要依次统计每个整数二进制中1的个数，然后将其相加即可得到位图中1的个数。

统计二进制中1的个数的方法如下：

  1. 将原数n与n - 1进行与运算得到新的 n 。
  2. 判断n是否为0，若 n 不为0则继续进行第一步。

如此进行下去，直到n最终为0，此时该操作进行了几次就说明二进制中有多少个1。

因为该操作每进行一次就会消去二进制中最右边的1

代码如下：

//获取被设置位的个数
size_t count(){size_t count = 0;//将每个整数中1的个数累加起来for (auto e : _bits){int num = e;//计算整数num中1的个数while (num){num = num&(num - 1);count++;}}return count; //位图中1的个数，即被设置位的个数
}
any、none、all

any成员函数用于判断位图中是否有位被设置。

我们只需遍历每一个整数，若这些整数全部都为0，则说明位图中没有位被设置过。
虽然位图可能并没有包含最后一个整数的全部比特位，但由于我们构造位图时是将整数的全部比特位都初始化成了0，因此不会对此处判断造成影响。

在这里插入图片描述

代码如下：

//判断位图中是否有位被设置
bool any(){//遍历每个整数for (auto e : _bits){//该整数中有位被设置if (e != 0) {return true;}		}return false; //全部整数都是0，则没有位被设置过
}

none成员函数用于判断位图中是否全部位都没有被设置。

位图中是否全部位都没有被设置，实际上就是位图中有位被设置的反面，因此none成员函数直接调用any成员函数，然后将返回值取反后再进行返回即可。

//判断位图中是否全部位都没有被设置
bool none() {return !any();
}

all成员函数用于判断位图中是否全部位都被设置。

判断过程分为两步：

  1. 先检查前n-1个整数的二进制是否为全1。
  2. 再检查最后一个整数的前N%32个比特位是否为全1。

需要注意的是，如果位图没有包含最后一个整数的全部比特位，那么最后一个整数的二进制无论如何都不会为全1，所以在判断最后一个整数时应该只判断位图所包含的比特位。

在这里插入图片描述

代码如下：

//判断位图中是否全部位都被设置
bool all() {size_t n = _bits.size();//先检查前n-1个整数for (size_t i = 0; i < n - 1; i++) {//取反后不为全0，说明取反前不为全1if (~_bits[i] != 0){return false;}}//再检查最后一个整数的前N%32位for (size_t j = 0; j < N % 32; j++) {//等于0表示没有被设置if ((_bits[n - 1] & (1 << j)) == 0){return false;}}return true;
}

打印函数

可以实现一个打印函数，便于检查我们上述代码的正确性，打印位图时遍历位图所包含的比特位进行打印即可，在打印位图的过程中可以顺便统计位图中位的个数count，将count与我们传入的非类型模板参数N进行比较，可以判断位图大小是否是符合我们的预期。

//打印函数
void Print() {int count = 0;size_t n = _bits.size();//先打印前n-1个整数for (size_t i = 0; i < n - 1; i++) {for (size_t j = 0; j < 32; j++) {if (_bits[i] & (1 << j)) {cout << "1";} else {cout << "0";}count++;}}//再打印最后一个整数的前N%32位for (size_t j = 0; j < N % 32; j++) {if (_bits[n - 1] & (1 << j)){cout << "1";}else{cout << "0";}count++;}cout << " " << count << endl;//打印总共打印的位的个数
}

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

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

相关文章

Linux-正则三剑客

Linux-正则三剑客

目录 一、正则简介 1.正则表达式分两类&#xff1a; 2.正则表达式的意义 二、Linux三剑客简介 1.文本处理工具&#xff0c;均支持正则表达式引擎 2.正则表达式分类 3.基本正则表达式BRE集合 4.扩展正则表达式ere集合 三、grep 1.简介 2.实践 3.贪婪匹配 四、sed …
阅读更多...
STM32Cubemx新建F429基础工程

STM32Cubemx新建F429基础工程

配置STM32CubeMX 配置KEY 配置USART1 配置RCC Project Manager Toolchain 选择 MDK-ARM Code Generator 配置如下 GENERATE CODE 即可 配置Keil5 魔术棒配置 – Target – 勾选 Use MicroLIB – Debug – Flash Download – 勾选Reset and Run 基础代码 /* Private incl…
阅读更多...
GD32F103x IIC通信

GD32F103x IIC通信

1. IIC通信 1.IIC的介绍 IIC总线有两条串行线&#xff0c;其一是时钟线SCK&#xff08;同步&#xff09;&#xff0c;其二是数据线SDA。只有一条数据线属于半双工。应用中&#xff0c;单片机常常作为主机&#xff0c;外围器件可以挂载多个。&#xff08;当然主机也可以有多个。…
阅读更多...
AJAX--Express速成

AJAX--Express速成

一、基本概念 1、AJAX(Asynchronous JavaScript And XML)&#xff0c;即为异步的JavaScript 和 XML。 2、异步的JavaScript 它可以异步地向服务器发送请求&#xff0c;在等待响应的过程中&#xff0c;不会阻塞当前页面。浏览器可以做自己的事情。直到成功获取响应后&#xf…
阅读更多...
【Spring MVC】MVC如何浏览器请求（service方法）

【Spring MVC】MVC如何浏览器请求（service方法）

文章目录 1. DispatcherServlet 的 service 方法1.1. processRequest 方法1.2. doService 方法 背景&#xff1a;平时我们学习 MVC 重点关注的时DispatcherServlet 的 doDispatcher 方法&#xff0c;但是在 doDispatcher 方法之前 还有请求处理的前置过程&#xff0c;这个过程…
阅读更多...
vue 使用 创建二维数组响应数据 渲染 echarts图标

vue 使用 创建二维数组响应数据 渲染 echarts图标

目前我遇到的情况就是用动态的二维数组数据渲染echarts图标&#xff0c;我们从后端收到的接口一般是个一维数组&#xff0c;需要手动构建并且保证响应式。接下来我做了个案例 一、案例总逻辑 1. 先创建一个vue项目 2. 添加 echarts依赖 3. 模拟数据请求&#xff0c;构建二维数组…
阅读更多...
Axios post请求出现500错误

Axios post请求出现500错误

笔者在编写前端form表单传后端数据的时候&#xff0c;出现了以下问题 一、问题场景 当我用axios发送post请求的时候&#xff0c;出现了500错误 笔者找了很长时间错误&#xff0c;代码没问题&#xff0c;后端接口也没问题&#xff0c;后来发现问题出在实体类上了 当前端post请…
阅读更多...
数据结构： 数组与链表

数据结构： 数组与链表

目录 1 数组 1.1 数组常用操作 1. 初始化数组 2. 访问元素 3. 插入元素 4. 删除元素 5. 遍历数组 6. 查找元素 7. 扩容数组 1.2 数组优点与局限性 1.3 数组典型应用 2 链表 2.1 链表常用操作 1. 初始化链表 2. 插入节点 3. 删除…
阅读更多...
10.03

10.03

代码 #include <iostream>using namespace std; class cz { private:int num1; //实部int num2; //虚部 public:cz(){}cz(int a,int b):num1(a),num2(b){}cz(const cz &other):num1(other.num1),num2(other.num2){}~cz(){}const cz operator(const cz &othe…
阅读更多...
websocket逆向【python实现http/https拦截】

websocket逆向【python实现http/https拦截】

python实现http拦截 前言：为什么要使用http拦截一、技术调研二、技术选择三、使用方法前言：为什么要使用http拦截 大多数爬虫玩家会直接选择API请求数据，但是有的网站需要解决扫码登录、Cookie校验、数字签名等，这种方法实现时间长，难度高。需求里面不需要高并发，有没有…
阅读更多...
5月22日比特币披萨日，今天你吃披萨了吗？

5月22日比特币披萨日，今天你吃披萨了吗？

比特币披萨日 1. Laszlo Hanyecz2. 最贵披萨诞生记3. 梭哈买披萨4. 未完待续 2010年5月22日&#xff0c;美国佛罗里达州的程序员Laszlo Hanyecz&#xff08;拉兹洛哈涅克斯&#xff09;用10000个比特币购买了棒约翰&#xff08;Papa Johns&#xff09;比萨店一个价值25美元的奶…
阅读更多...
C语言：选择+编程（每日一练Day9）

C语言：选择+编程（每日一练Day9）

目录 选择题&#xff1a; 题一&#xff1a; 题二&#xff1a; 题三&#xff1a; 题四&#xff1a; 题五&#xff1a; 编程题&#xff1a; 题一&#xff1a;自除数 思路一&#xff1a; 题二&#xff1a;除自身以外数组的乘积 思路二&#xff1a; 本人实力有限可能对…
阅读更多...
C++核心编程--继承篇

C++核心编程--继承篇

4.6、继承 继承是面向对象三大特征之一 有些类与类之间存在特殊的关系&#xff0c;例如下图中&#xff1a; ​ 我们发现&#xff0c;定义这些类的定义时&#xff0c;都拥有上一级的一些共性&#xff0c;还有一些自己的特性。那么我们遇到重复的东西时&#xff0c;就可以考虑使…
阅读更多...
OpenCV读取图像时按照BGR的顺序HWC排列,PyTorch按照RGB的顺序CHW排列

OpenCV读取图像时按照BGR的顺序HWC排列,PyTorch按照RGB的顺序CHW排列

OpenCV读取RGB图像 在OpenCV中&#xff0c;读取的图片默认是HWC格式&#xff0c;即按照高度、宽度和通道数的顺序排列图像尺寸的格式。我们看最后一个维度是C&#xff0c;因此最小颗粒度是C。 例如&#xff0c;一张形状为2562563的RGB图像&#xff0c;在OpenCV中读取后的格式…
阅读更多...
R | R及Rstudio安装、运行环境变量及RStudio配置

R | R及Rstudio安装、运行环境变量及RStudio配置

R | R及Rstudio安装、运行环境变量及RStudio配置 一、介绍1.1 R介绍1.2 RStudio介绍 二、R安装2.1 演示电脑系统2.2 R下载2.3 R安装2.4 R语言运行环境设置&#xff08;环境变量&#xff09;2.4.1 目的2.4.2 R-CMD测试2.4.3 设置环境变量 2.5 R安装测试 三、RStudio安装3.1 RStu…
阅读更多...
【pwn入门】用gdb实现第1个pwn

【pwn入门】用gdb实现第1个pwn

声明 本文是B站你想有多PWN学习的笔记&#xff0c;包含一些视频外的扩展知识。 有问题的源码 #include <stdio.h> #include <stdlib.h> #include <unistd.h> char sh[]"/bin/sh"; int func(char *cmd){system(cmd);return 0; }int main(){char …
阅读更多...
【操作系统】进程同步与进程互斥

【操作系统】进程同步与进程互斥

&#x1f40c;个人主页&#xff1a; &#x1f40c; 叶落闲庭 &#x1f4a8;我的专栏&#xff1a;&#x1f4a8; c语言 数据结构 javaEE 操作系统 Redis 石可破也&#xff0c;而不可夺坚&#xff1b;丹可磨也&#xff0c;而不可夺赤。 进程同步与进程互斥 一、什么是进程同步二、…
阅读更多...
redis中list类型的操作

redis中list类型的操作

一、特点 Redis列表是简单的字符串列表&#xff0c;按照插入顺序排序。你可以添加一个元素到列表的头部&#xff08;左边&#xff09;或者尾部&#xff08;右边&#xff09;。一个列表最多可以包含 2^32 - 1 个元素 (超过40亿个元素)。 list其底层使用quicklist存储数据 qu…
阅读更多...
力扣-383.赎金信

力扣-383.赎金信

Idea 使用一个hashmap 或者一个int数组存储第二次字符串中每一个字符及其出现的次数 遍历第一个字符串&#xff0c;讲出现的重复字符减1&#xff0c;若该字符次数已经为0&#xff0c;则返回false AC Code class Solution { public:bool canConstruct(string ransomNote, strin…
阅读更多...
色彩一致性自动处理方法在遥感图像中的应用

色彩一致性自动处理方法在遥感图像中的应用

前言 在获取卫星遥感影像时&#xff0c;由于受不均匀的光照、不同的大气条件和不同的传感器设备等因素的影响&#xff0c;遥感影像中会存在局部亮度和色彩分布不均匀的现象&#xff0c;下面是在BigMap地图下载器中收集的几幅谷歌卫星影像&#xff0c;像下面这种都是拼接好的影像…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发