目录

1.位图的引入

2.位图概念

3.位图的实现

3.1前提准备

3.2set

3.3reset

3.4test

4.位图的应用

---

1.位图的引入

给40亿个不重复的无符号整数，没排过序

再给一个无符号整数，如何快速判断这个无符号整数是否在 这40亿个数中

首先，一个无符号整数占4个字节，40亿个无符号整数占160亿字节

其次，1GB = 1024MB = 1024*1024KB = 1024*1024*1024Byte 约等于 10亿+ 字节

那么40亿个无符号整数需要约16G的内存，超出普通计算机的容量，更别提

使用哈希(指针等额外开销)、排序后二分查找(内存压力未解决)判断，

解决方法：使用位图标记

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一 个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0 代表不存在

2.位图概念

位图就是用比特位表示一个数据的状态信息，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的

位图就是将数据与数据在位图中对应的比特位进行了一一对应，是哈希的一种变形

3.位图的实现

用字节进行位运算，我们可以操纵某一个比特位为0或者为1

因为位运算操作的是数据的二进制位模式，而非内存中的字节顺序，所以我们不必关注端序

只是在画图的时候需要关注一下端序(大小端)

3.1前提准备

#pragma once
#include<vector>
namespace dfq
{template<size_t N>class bitset{public:bitset(){_a.resize(N / 32 + 1);}private:vector<int> _a;};
}

(1)C++库里面有 bitset 的实现，创建命名空间避免命名冲突
(1)非类型模板参数N表示要开多大的空间
(1)使用一个整型或者char类型的数组，通过字节位运算操纵比特位
(1)构造函数，向上取整开空间

3.2set

//将x映射的那个位置变为1
void set(size_t x)
{size_t i = x / 32;//i标识x映射到_a的第几个位置size_t j = x % 32;//j标识x映射到4个字节中的哪一个位置_a[i] |= (1 << j);
}

(1)  i 标识x映射到_a的第几个位置
(2) j 标识x映射到4个字节中的哪一个位置

(3) 数组中对应数据的对应二进制位变为1

| 或运算的特点，有1为1，0与其他数进行或运算等于其他数本身
<< 左移运算符的特点，数据的二进制为向高位移动，左边舍弃，右边补0

......... 0 ...........   == _a[i]00000000001000000000000   == 1 << j

3.3reset

//将x映射的那个位置变为0
void reset(size_t x)
{size_t i = x / 32;//i标识x映射到_a的第几个位置size_t j = x % 32;//j标识x映射到4个字节中的哪一个位置_a[i] &= ~(1 << j);
}

(1) 数组中对应数据的对应二进制位变为0

& 与运算的特点，有0为0，1与其他数进行与运算等于其他数本身
<< 左移运算符的特点，数据的二进制为向高位移动，左边舍弃，右边补0

~ 按位取反运算特点，数据的二进制位 1 变 0，0变1

......... 1 ...........   == _a[i]00000000001000000000000   == 1 << j11111111110111111111111   == ~(1 << j)

3.4test

bool test(size_t x)
{size_t i = x / 32;//i标识x映射到_a的第几个位置size_t j = x % 32;//j标识x映射到4个字节中的哪一个位置return _a[i] & (1 << j);
}

_a[i] & (1 << j) 的意思是：

数据存在，数组中对应数据的对应比特位为1，表达式不为0，为真

数据不存在，数组中对应数据的对应比特位为0，表达式为0，为假

4.位图的应用

1. 给定100亿个整数，设计算法找到只出现一次的整数？

(1)使用两个位图 bs1、bs2 (根据范围开空间)

(2)从文件中读取数据，调用set函数进行标记，标记原理及规则如下：

bs1、bs2对应的比特位一个有 00、01、10、11四种情况，我们取前面三种

• 初始条件下，bs1、bs2比特位均为0
• 数据第一次出现(!_bs1.test(x) && !_bs2.test(x))，bs2.set(x)
• 数据第二次出现(!_bs1.test(x) && _bs2.test(x))，bs1.set(x);bs2.reset(x)
• 三次以上就不进行统计了

(3)bs1、bs2对应的比特位组合为01的数就是只出现一次的整数

template<size_t N>
class twobitset
{
public://x映射的那个值变为1void set(size_t x){//00 -> 01if (!_bs1.test(x) && !_bs2.test(x))_bs2.set(x);//01 -> 10else if (!_bs1.test(x) && _bs2.test(x)){_bs1.set(x);_bs2.reset(x);}//10 就不变了}//检测x是否只存在一次bool is_once(size_t x){return !_bs1.test(x) && _bs2.test(x);}private:bitset<N> _bs1;bitset<N> _bs2;
};

2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

将两个序列分别映射到两个位图上，对两个位图的每个字节进行按位与操作，结果为1 的比特位对应的数据的就是两个序列的交集

3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整 数

与第一题的思路一致，使用两个位图统计次数，00、01、10、11

• 初始条件下，bs1、bs2比特位均为0
• 数据第一次出现(!_bs1.test(x) && !_bs2.test(x))，bs2.set(x)
• 数据第二次出现(!_bs1.test(x) && _bs2.test(x))，bs1.set(x);bs2.reset(x)
• 数据第三次出现(_bs1.test(x) && !_bs2.test(x))，bs2.set(x)
• 四次以上就不进行统计了

总结位图的应用：

1. 快速查找某个数据是否在一个集合中

2. 排序 + 去重

3. 求两个集合的交集、并集等

4. 操作系统中磁盘块标记