【C++】位图

位图概念

位图（bitmap），又称位数组或位向量，是一种数据结构。它利用连续的位（bit）来高效地表示一组布尔值（即0和1）。在位图中，每一位都对应一个可能的元素或状态，通过将该位设置为1或0来表示该元素是否存在或某个状态是否激活。

适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

面试题：

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

给出以下方法：

• 遍历O(N)。
• 排序O(N log_2 N)+二分查找O(log_2 N)。
• set O(log_2 N)、unordered_set O(1)。

以上方法都有一个问题，数据量太大，放不到内存中。40亿个无符号整数，约占用16G内存

位图解决思路：

将数据使用直接定址法映射到数组相应的位置。时间复杂度O(1)。

数组要开多大的空间呢？

开数据范围大小的空间，才能满足所有的数据都能映射到相应的位置。

无符号整数的取值范围为0~4294967295（2^32-1)。所以要开2^32个空间。

开2^32个整型大小的空间（约16G）吗？空间还是不够。数据是否在给定的整型数据中，结果是在或不在，正好是两种状态，使用标志位来表示数据的状态即可，每一位都对应一个元素的状态，此时，只需要开2^32个位大小的空间（约16G/4*32=500MB）

实现位图

bitmap（）

• 给所有整数开空间

数组可以定义的最小单位是Byte，并不是bit位。我们数组中依旧存放int类型，一个int占4个Byte，32个bit位。

namespace zxa
{class bitmap{public:bitmap(size_t N){_bits.resize(N, 0);//error_num = 0;}private:std::vector<int> _bits;size_t _num;//映射存储了多少个数据};
}

_bits.resize(N, 0);//error

这样并不是开N个位大小的空间，而是开了N个整型大小的空间。比如N=100时，我们是想开100个bit位来表示这100个整数在不在的状态，此时，却开了100个int，3200bit的大小。

_bits.resize(N / 32, 0);//error

这样也不对，比如N在0~32个之间（不包括32），那么一个Byte都没有开出来。比如，N=100时，开了100/32=3个int、3*4*8=96bit位的大小，但是，如果整数为97~99，要映射哪个位置？就越界了。

_bits.resize(N / 32 + 1, 0);

永远多开1个int、32bit大小的空间。 

set（）

• 将整数x映射的位置置为1

注意：数组中存放的是一个一个整型，而不是一个位一个位存的。

//将x映射的位置置为1
void set(size_t x)
{size_t index = x / 32;//计算x映射的位在第几个整型size_t pos = x % 32;//计算x在这个整型的第几位_bits[index] |= (1 << pos);//将该位置为1
}

reset（）

• 将整数x映射的位置置为0。 

注意：不排除删除了x之后，又删除x。（也就是x映射的位置本来就为0，又将x映射位置置为0）

//将x映射的位置置为0
void reset(size_t x)
{size_t index = x / 32;size_t pos = x % 32;_bits[index] &= ~(1 << pos);//_bits[index] = (_bits[index]|(1 << pos))^(1 << pos);也可以
}

test（）

• 判断整数x在不在。（也就是判断x映射的位置是否为1） 

//判断x在不在（x映射的位置是否为1）
bool test(size_t x)
{size_t index = x / 32;size_t pos = x % 32;return _bits[index] & (1 << pos);
}

完整代码+测试

bitmap.hpp:

#pragma once
#include<vector>namespace zxa
{class bitmap{public://给N个整数开空间bitmap(size_t N){//_bits.resize(N, 0);//_bits.resize(N / 32, 0);_bits.resize(N / 32 + 1, 0);_num = 0;}//将x映射的位置置为1void set(size_t x){size_t index = x / 32;//计算x映射的位在第几个整型size_t pos = x % 32;//计算x在这个整型的第几位_bits[index] |= (1 << pos);//将将该位置为1}//将x映射的位置置为0void reset(size_t x){size_t index = x / 32;size_t pos = x % 32;_bits[index] &= ~(1 << pos);//_bits[index] = (_bits[index]|(1 << pos))^(1 << pos);也可以}//判断x在不在（x所在位是否为1）bool test(size_t x){size_t index = x / 32;size_t pos = x % 32;return _bits[index] & (1 << pos);}private:std::vector<int> _bits;size_t _num;//映射存储了多少个数据};void test_bitmap();
}

test.cpp:

#define _CRT_SECURE_NO_WARNINGS 
#include"bitmap.hpp"//测试，以100个无符号整数为例
void zxa::test_bitmap()
{bitmap bm(100);bm.set(99);bm.set(98);bm.set(95);bm.reset(98);for (size_t i = 0; i < 100; i++){printf("[%d]:%d\n", i, bm.test(i));}
}
int main()
{zxa::test_bitmap();return 0;
}

结果：

对于一开始的面试题，40亿个整数理论都存在文件中，然后从文件中读取，这里不是很好做演示。

位图的应用

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

补充

如何表示整数2^32

表示整数 2^32 （4,294,967,296）的方式。

unsigned long long x = 1;
for (size_t i = 0; i < 32; ++i)
{x *= 2;
}
bitmap bm(x);
bitmap bm(-1);
bitmap bm(0Xffffffff);
bitmap bm(pow(2, 32));

位运算基本运算规则

• 按位与 &：   全1为1，有0则0。
• 按位或 |：     有1则1，全0为0。
• 按位异或 ^： 相同为0，相异为1。
• 按位取反 ~：1取反为0，0取反为1。
• 左移 <<：      将一个二进制数的所有位向高位移动指定的位数。
• 右移 >>：      将一个二进制数的所有位向低位移动指定的位数。

位运算都是针对的二进制位，左移右移不是左右方向移位，而是向高位移动。