目录

一、位图的引入

二、位图的应用

三、位图的使用（bitset的使用）

3.1 介绍

 3.2 使用

四、bitset（位图模拟实现）

一、位图的引入

面试题【腾讯】：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中

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

• j进行遍历，时间复杂度O(N)
• 将这一堆数进行排序，然后通过二分查找的方法判断该数是否在这一堆数中，排序(O(NlogN))，利用二分查找: logN
• 将这一堆数插入到unordered_set容器中，查找时间复杂度O(1)

从方法上来看，这些方法都是可以的，问题是这里有40亿个无符号整数，若是我们要将这些数全部加载到内存当中，那么将会占用最小16G的空间，空间消耗极大，普通计算机内存也没有这么大，所以实际上是不可行的

 这里解决方法是：位图解决

位图概念

所谓位图，就是用每一位比特位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的 ，位图实际上也是使用哈希思想，只不过是哈希的变形

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

1字节 = 8bit，代表的整数就是0~7，比特位为1则表示该数存在

无符号整数总共有 2^32 个，接近43亿，因此记录这些数字就需要 2^32 个比特位，也就是512M的内存空间，内存消耗大大减少，也就是说上面的问题可以用位图快速解决

二、位图的应用

位图可以应用于以下场景：

1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记

三、位图的使用（bitset的使用）

3.1 介绍

在STL中，C++提供了 bitset，也就是位图

文档介绍链接：bitset - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/bitset/bitset/?kw=bitset

bitset的解释： 

bitset的模板参数是一个非类型模板参数，是一个无符号整数

bitset的常用接口：

set：设置指定位或所有位

reset：清空指定位或所有位

test：获取指定位的状态

其他有需求再查询文档

使用bitset需要包含头文件：

#include <bitset>

 3.2 使用

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

简单测试代码：

#include <iostream>
#include <bitset>
using namespace std;int main()
{//构造一个8位的位图，所有位都初始化为 00000000bitset<8> bs1;//构造一个16位的位图，所有位都初始化为 0000000000000000bitset<16> bs2; bitset<8> bs;bs.set(2); //设置第2位为1bs.set(4); //设置第4位为1bs.set(0); //设置第0位为1cout << bs << endl; //10010100bs.reset(0); //清空第0位cout << bs << endl; //00010100cout << bs.test(3) << endl; //获取第三位状态return 0;
}

运行结果

下面进行对上面例子进行测试：

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

void Test()
{//bitset<-1> bs; //模板参数是无符号整数 size_t，-1代表无符号整数最大的范围，接近43亿bitset<0xffffffff> bs;//也可以使用0xffffffff，也是无符号整数的最大范围bs.set(100);//设置第100位为1bs.set(100000);//设置第100000位为1bs.set(888888);//设置第888888位为1cout << bs.test(100) << endl; //获取第100位状态cout << bs.test(100000) << endl; //获取第100000位状态cout << bs.test(888888) << endl; //获取第888888位状态cout << endl;bs.reset(100000);//清空第100000位cout << bs.test(100) << endl; //获取第100位状态cout << bs.test(100000) << endl; //获取第100000位状态cout << bs.test(888888) << endl; //获取第888888位状态
}

注意：VS可能需要需要改一下堆栈最大的空间大小，否则会栈溢出，运行不了

VS设置如下：

1）选择 "项目->属性".

（2）选择 "链接器".

（3）选择 "系统".

4）在 "堆栈保留大小"中输栈的大小，例如： 1GB为1073741824字节（1024 * 1024 * 1024）

5）重新生成项目

运行结果

四、bitset（位图模拟实现）

实现框架如下：

//使用命名空间，防止与库发生冲突
namespace fy
{template<size_t N>class bitset{public://构造bitset(){}//设置 x 位为1void set(size_t x){}//清楚 x 位的1，也就是置0void reset(size_t x){}//检测某一位的状态bool test(size_t x){}private:vector<char> _bits;//每个类型都是char};
}

构造函数 

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

一个char有8个比特位，因此N个位的位图就需要用到N/8个char，但是实际我们所需的char个数是N/32+1，比如，有18个整数，映射需要18个bit，一个char 是8bit，18/8=2，还剩下2个整数，所以char 的个数需要+1

代码如下：

//构造
bitset()
{//默认开N/8+1个char，全部置0_bits.resize(N / 8 + 1, 0);//_bits.resize((N >> 3) + 1, 0);
}

set函数

set函数用于设置指定位 

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

代码如下： 

//设置 x 位为1
void set(size_t x)
{size_t i = x / 8;//在第几个char//size_t i = x >> 3;//也可以这么写size_t j = x % 8;//在char的第几位_bits[i] |= (1 << j);//将该位设置为1（不影响其他位）
}

 reset函数

reset函数用于清空指定位 

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

代码如下：

//清除 x 位的1，也就是置0
void reset(size_t x)
{size_t i = x / 8;//在第几个char//size_t i = x >> 3;//也可以这么写size_t j = x % 8;//在char的第几位_bits[i] &= (~(1 << j));//将该位设置为0（不影响其他位）
}

test函数

test函数用于获取位的状态 

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

代码如下

//检测某一位的状态
bool test(size_t x)
{size_t i = x >> 3;size_t j = x % 8;return _bits[i] & (1 << j);
}

 测试代码

void Test_bitset(){bitset<0xffffffff> bs;bs.set(10);bs.set(10000);bs.set(8888);cout << bs.test(10) << endl;cout << bs.test(10000) << endl;cout << bs.test(8888) << endl;cout << bs.test(8887) << endl;cout << bs.test(9999) << endl << endl;bs.reset(8888);bs.set(8887);cout << bs.test(10) << endl;cout << bs.test(10000) << endl;cout << bs.test(8888) << endl;cout << bs.test(8887) << endl;cout << bs.test(9999) << endl;}

运行结果

查看一下内存资源，调试下查看，使用了512MB的内存

完整代码

#pragma once
#include <vector>
//使用命名空间，防止与库发生冲突
namespace fy
{template<size_t N>class bitset{public://构造bitset(){//默认开N/8+1个char，全部置0_bits.resize(N/8+1, 0);//_bits.resize((N >> 3) + 1, 0);//也可以这么写，要注意优先级}//设置 x 位为1void set(size_t x){size_t i = x / 8;//在第几个char//size_t i = x >> 3;//也可以这么写size_t j = x % 8;//在char的第几位_bits[i] |= (1 << j);//将该位设置为1（不影响其他位）}//清除 x 位的1，也就是置0void reset(size_t x){size_t i = x / 8;//在第几个char//size_t i = x >> 3;//也可以这么写size_t j = x % 8;//在char的第几位_bits[i] &= (~(1 << j));//将该位设置为0（不影响其他位）}//检测某一位的状态bool test(size_t x){size_t i = x >> 3;size_t j = x % 8;return _bits[i] & (1 << j);}private:vector<char> _bits;//每个类型都是char};void Test_bitset(){bitset<0xffffffff> bs;bs.set(10);bs.set(10000);bs.set(8888);cout << bs.test(10) << endl;cout << bs.test(10000) << endl;cout << bs.test(8888) << endl;cout << bs.test(8887) << endl;cout << bs.test(9999) << endl << endl;bs.reset(8888);bs.set(8887);cout << bs.test(10) << endl;cout << bs.test(10000) << endl;cout << bs.test(8888) << endl;cout << bs.test(8887) << endl;cout << bs.test(9999) << endl;}
}

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新