位图简介及其应用和模拟实现方法

位图的介绍和模拟实现

• 位图的基本概念
  • • 位图在实际场景中的应用

  • 位图的操作方式

  • • 位图的定义与特性
    • 位图所包含的成员函数
    • 对位图运算符的使用方法

  • 位图的仿真实现过程

  • • 构造函数的设计与实现
    • set、reset、filp 等操作函数
    • size、count 等相关函数

位图概念与特性

经典面试问题：
现有40亿个互不相同的无符号整数，且未进行排序。若给出一个无符号整数，如何高效判断该数是否存在于这40亿个数值中。

常规解决方案包括：

1. 先对数据进行排序，再通过二分查找方式定位目标值
2. 将所有数据加载至unorder_set结构中，利用find函数进行检索以确认是否存在
   方案1所需时间复杂度为：排序阶段O(NlogN)，查找阶段O(logN)
   方案2所需时间复杂度为：O(N)
   上述两种方法虽在理论上可行，但考虑到40亿个无符号整数将占用约16GB的内存空间，这种存储需求显然过高，因此上述方法难以实际应用。

此时可采用位图技术予以解决

判断某一数据是否存在于指定整型集合中，其结果仅有两种可能——存在或不存在。这恰好与二进制比特位的两种状态相对应。因此可以通过设置一个二进制比