• 【C++】位图详解（一文彻底搞懂位图的使用方法与底层原理）

    目录

    1.位图的概念

    2.位图的使用方法

    定义与创建

    设置和清除

    位访问和检查

    转换为其他格式

    3.位图的使用场景

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

    2.排序+去重

    3.求两个集合的交集和并集

    4.位图的底层实现

    私有成员定义与初始化

    set和reset的实现

    前面的博客我们介绍了哈希结构以及以哈希为底层结构的容器unordered_map和unordered_set，相较于以红黑树为底层的map和set，它们的优势是更高效的查找（平均为O(1)）不过代价是更多内存的消耗，这些内存的消耗在某些场景下会变得致命：

    这是一道腾讯的面试题：

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

    既然是追求高效的查询，显然哈希结构更具优势，但是在这里如果使用哈希表，会占用大量的内存。40亿个整数键需要16GB的内存，为了解决哈希冲突，实际所需容量会更多（1.5倍以上）。这是什么概念呢？

    这是博主的笔记本规格，可以看到RAM（运行内存）刚好是16GB（加上虚拟内存也不过20GB左右），也就是说即使我“倾家荡产”也不足以实现上述操作。

    用其他办法（比如压缩数据结构）的确可以节省内存的占用，但是并无法达到快速查询的效果。现在存在如下矛盾：

    ①：更快查询效率的需要

    ②：更少内存占用的需要

    我们需要寻找一种办法，同时满足上述两种需求，以解决这个问题。于是乎，位图闪亮登场~

    1.位图的概念

    所谓位图，是一种使用二进制位（bit位）来表示数据状态的数据结构。其每一个二进制位（bit）可以表示一个数据的存在与否，从而通过极少的内存实现大规模数据的存储与处理。

    比如，存储1个整形需要4个字节的空间，现在我用存储1个整形的空间，就可以表示32个整形元素的存储状态：

    1个整形有32个bit位，每一位都可以表示一个数据的状态（数据1存在就让第一位bit值变成1），因此我们可以把每一个比特位都看成一个bool值，bool值为1表示数据存在，为0表示不存在。

    现在我们回到上面那道问题：

    原本需要16GB的空间存储40亿个整数，而1个整形的空间可以表示32个数据的存在状态，所以现在只需要 16GB/32 = 512KB 的存储空间，而且由于数据是映射存储的，我们想知道 整数x 存不存在，只需要看第 x 个比特位是否为1即可，所以查询的时间复杂度是O(1)。这种映射关系和哈希结构很像，所以位图实际上就是哈希的一种应用。

    总结：位图是如何查询到数据的

    位图只存储数据的状态（即是否存在），而不存储数据本身的值，但是我们仍可以根据位图的位索引位置间接查询到数据本身。比如要记录整数 5 是否存在，则位图第 5 位会被置为 1，看到第 5 位是 1，可以知道 5 存在，但位图中并没有存储“5”的数值。总之，我们并不是根据数据本身进行查询，而是通过位置映射关系进行查询。

     

    2.位图的使用方法

    C++标准库提供了一个名为 bitset 的数据结构，用于管理和操作bit数组，可用于实现位图。

    以下是bitset使用方法的介绍：

    定义与创建

    bitset 是一个模版类，模版参数表示位数，在编译时确定大小，例如：

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. int main()
    6. {
    7. 	bitset<8> bits;             // 定义一个大小为 8 位的位图（位数组）
    8. 	bitset<16> bits16(0xF0F0);  // 定义一个大小为 16 位的位图，并初始化为二进制 1111 0000 1111 0000
    9. 	bitset<8> bitsFromStr("10101010"); // 从字符串创建一个 8 位位图
    10.  
    11. 	return 0;
    12. }

    设置和清除

    bitset 提供了很多方法用于位操作和状态管理：

    set()将所有位设置为 1
    set(size_t pos, bool value = true)将指定位置 pos 的位设置为 value
    reset()将所有位重置为 0
    reset(size_t pos)将指定位置 pos 的位重置为 0
    flip()将所有位翻转（0 变 1，1 变 0）
    flip(size_t pos)将指定位置 pos 的位翻转

     

     

     

     

     

     

     

    1. 	bitset<8> bits("10101010");
    2. 	bits.set(0);        // 将第 0 位设置为 1，结果为 10101011
    3. 	bits.reset(1);      // 将第 1 位设置为 0，结果为 10101001
    4. 	bits.flip();        // 翻转所有位，结果为 01010110
    5. 	bits.flip(2);       // 翻转第 2 位，结果为 01010010

     

    位访问和检查

    operator[]使用 [] 访问位
    test(size_t pos)测试指定位置的位是否为 1，返回 true 表示为 1，返回 false 表示为 0
    all()检查所有位是否都为 1，是返回 true，否则返回 false
    any()检查是否存在至少一位为 1，是则返回 true
    none()检查是否所有位都是 0，是则返回 true
    count()返回所有 1 的数量

     

    转换为其他格式

    to_string()将位图转换为字符串
    to_ulong()将位图转换为 unsigned long 类型
    to_ullong()将位图转换为 unsigned long long 类型

    3.位图的使用场景

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

    现在随机生成10000个范围在0~15000的整数，检验某些数据是否存在：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6.  
    7. using namespace std;
    8.  
    9. int main() {
    10.     const int num_elements = 10000; // 元素数量
    11.     const int min_value = 0;         // 最小值
    12.     const int max_value = 15000;     // 最大值
    13.  
    14.     // 获取当前时间作为种子
    15.     unsigned seed = static_cast<unsigned>(std::chrono::system_clock::now().time_since_epoch().count());
    16.     std::mt19937 gen(seed); // 使用当前时间作为种子生成随机数
    17.  
    18.     std::uniform_int_distribution<> dis(min_value, max_value); // 均匀分布
    19.  
    20.     // 创建一个 vector 并填充随机数
    21.     std::vector<int> nums(num_elements);
    22.     for (int& number : nums) {
    23.         number = dis(gen); // 生成随机数并赋值
    24.     }
    25.  
    26.     // 创建位图，范围是 0 到 max_value
    27.     bitset bitset;
    28.  
    29.     // 将生成的随机数映射到位图中
    30.     for (const auto& it : nums) {
    31.         bitset.set(it);
    32.     }
    33.  
    34.     // 检查某个数是否存在
    35.     vector<int> num_test = { 5, 64, 862, 1356, 45, 236, 856, 12, 489, 6116, 1648, 216, 1554, 335, 795, 211 };
    36.     cout << "存在性检查结果：\n";
    37.     for (const auto& it : num_test) {
    38.         if (bitset.test(it)) {  // 检查 num 的位是否为 1
    39.             cout << it << " 存在.\n";
    40.         }
    41.         else {
    42.             cout << it << " 不存在.\n";
    43.         }
    44.     }
    45.  
    46.     return 0;
    47. }

    分别运行三次的结果： 

    2.排序+去重

    位图和哈希表底层都是哈希结构，为什么哈希表不能实现排序而位图可以呢？

    因为哈希表的存储位置是通过哈希函数求得的的哈希值决定的，不同的元素可能有相同的哈希值，因此元素的存储是非线性的。

    而位图的存储位置就是数据本身决定的，每个比特位对于一个元素，因此元素的存储是线性的。

    下面来看示例：

    1. #include 
    2. using namespace std;
    3. #include 
    4. #include 
    5.  
    6. const size_t MAX_SIZE = 1000;  // 数据范围是 0 到 1,000,000
    7.  
    8. int main() {
    9.     bitset bitset;
    10.  
    11.     // 模拟数据插入（包括重复数据）
    12.     vector<int> data = { 566,254,4,26,326,2,495,56,98,26,254,566,235,66 };
    13.     cout << "排序+去重前的数据:\n";
    14.     for (auto it : data) {
    15.         cout << it << " ";
    16.     }
    17.     cout << "\n";
    18.  
    19.     for (int num : data) {
    20.         bitset.set(num);  // 将数据映射到位图中
    21.     }
    22.  
    23.     // 遍历位图，输出所有置位为 1 的位置（即有序的、去重的数据）
    24.     cout << "排序+去重后的数据:\n";
    25.     for (size_t i = 0; i < MAX_SIZE; ++i) {
    26.         if (bitset.test(i)) {
    27.             cout << i << " ";
    28.         }
    29.     }
    30.     cout << "\n";
    31.  
    32.     return 0;
    33. }

     

    3.求两个集合的交集和并集

    位图是如何完成交集并集运算的呢？由于位图的每一个bit位存储对应元素的bool值（0或1），而相同元素在不同位图中的存储位置是一样的，我们对两个位图进行按位与运算，就可以得到交集；进行按位或运算，就可以得到并集。

    1. #include 
    2. #include 
    3. const size_t MAX_SIZE = 1000000;
    4. using namespace std;
    5.  
    6. int main() {
    7.     bitset setA;
    8.     bitset setB;
    9.  
    10.     // 插入一些数据到集合 A
    11.     setA.set(123456);
    12.     setA.set(654321);
    13.     setA.set(500);
    14.  
    15.     // 插入一些数据到集合 B
    16.     setB.set(654321);
    17.     setB.set(500);
    18.     setB.set(999999);
    19.  
    20.     // 求交集（A & B）
    21.     bitset intersection = setA & setB;
    22.     cout << "交集:\n";
    23.     for (size_t i = 0; i < MAX_SIZE; ++i) {
    24.         if (intersection.test(i)) {
    25.             cout << i << " ";
    26.         }
    27.     }
    28.     cout << "\n";
    29.  
    30.     // 求并集（A | B）
    31.     bitset unionSet = setA | setB;
    32.     cout << "并集:\n";
    33.     for (size_t i = 0; i < MAX_SIZE; ++i) {
    34.         if (unionSet.test(i)) {
    35.             cout << i << " ";
    36.         }
    37.     }
    38.     cout << "\n";
    39.  
    40.     return 0;
    41. }

    4.位图的底层实现

    位图的底层其实是一个vector容器，容器内部存放整形元素，一个整形元素可以存放32个对应元素的状态（bool值），并且通过位运算实现映射关系的对应。

    底层存储结构：

    私有成员定义与初始化

    在bitset类中，我们需要一个_bitCount成员表示比特位的总个数用于对bitset的初始化，以及一个_bit（vector类型的容器 ）用于存储元素。

    1. class bitset
    2. {
    3.  
    4. private:
    5. 	vector<int> _bit;
    6. 	size_t _bitCount;
    7. };

    位图的大小是固定的，根据_bitCount的大小进行空间开辟，而_bitCount的大小是由待存储元素的最大值决定的。但是_bitCount的单位是bit，而vector中存储单位是整形，所以我们需要进行换算，将_bitCount>>5（也就是除以2^5）并+1（由于除法会向下取整，例如 bitCount 是 33，33 >> 5 计算结果是 1，但我们实际上需要 2 个整型来存储 33 个比特位）

    1. 	bitset(size_t bitCount)
    2. 		: _bit((bitCount >> 5) + 1), _bitCount(bitCount)
    3. 	{}

    set和reset的实现

    假设用which表示要存储的元素，我们需要求得映射位置。我们可以把每个元素当成一个数组，数组中包含32个比特位，此时将which/32就可以得出存储在第几个数组中，并用which%32得到在该数组下的具体比特位，假设which = 152：

    存储位置为v[4]的第24个比特位：

    如此一来就找到了对应的映射关系。下面是代码部分：

    1. 	// 将which比特位置1
    2. 	void set(size_t which)
    3. 	{
    4. 		if (which > _bitCount)
    5. 			return;
    6. 		size_t index = (which >> 5);
    7. 		size_t pos = which % 32;
    8. 		_bit[index] |= (1 << pos); // 将对应bit位改为1
    9. 	}
    10. 	// 将which比特位置0
    11. 	void reset(size_t which)
    12. 	{
    13. 		if (which > _bitCount)
    14. 			return;
    15. 		size_t index = (which >> 5);
    16. 		size_t pos = which % 32;
    17. 		_bit[index] &= ~(1 << pos); // 将对应bit位改为0
    18. 	}
    19. 	// 检测位图中which是否为1
    20. 	bool test(size_t which)
    21. 	{
    22. 		if (which > _bitCount)
    23. 			return false;
    24. 		size_t index = (which >> 5);
    25. 		size_t pos = which % 32;
    26. 		return _bit[index] & (1 << pos);
    27. 	}
    28. 	// 获取位图中比特位的总个数
    29. 	size_t size()const { return _bitCount; }
    30.

    以上就是对位图的详细介绍说明，欢迎指正~

    码文不易，还请多多关注支持，这是我持续创作的最大动力！

  • 相关阅读:
    如何实现外网连接公司内网的ERP系统？快解析内网穿透
    PHP如何批量修改二维数组中值
    数据结构题目收录（二十）
    k8s中kubectl陈述式资源管理
    3D激光SLAM：LeGO-LOAM论文解读---硬件系统部分
    【数据结构】链表-基本定义及代码练习
    ASP.NET Core 分层服务注入思想实现
    Feign负载均衡
    python篇-自动化-poco
    【C++】obj模型文件解析（tiny_obj_loader）
  • 原文地址：https://blog.csdn.net/dhgiuyawhiudwqha/article/details/143434187