【高效数据结构——位图bitmap】

初识位图bitmap

位图（Bitmap）是一种用于表示和操作位（bit）的数据结构。它是由一系列二进制位（0 或 1）组成的序列，每个位都可以单独访问和操作。

位图常用于以下情况：

• 压缩存储：位图可以有效地存储大量的布尔值信息，每个位只占用一个比特，因此可以大幅减少存储空间的占用。例如，当需要存储大量的开关状态、标志位或者布尔型数据时，使用位图可以节省内存。

• 快速查找和查询：由于位图的特殊存储结构，它可以快速进行位的查找和查询。例如，可以用位图表示一组元素的存在与否，然后通过位运算来快速进行成员的查找、去重、交集、并集等操作。

• 数据压缩和索引：位图可以用于压缩和索引数据，特别是在数据集合较小且有规律的情况下。例如，在数据库中，可以使用位图索引来加速数据的查询操作。

• 布隆过滤器：布隆过滤器是一种基于位图的概率型数据结构，用于快速判断一个元素是否存在于一个集合中。它通过多个哈希函数和位图来判断元素的存在性，具有较低的空间占用和高效的查询速度。

在实现位图时，常用的数据结构有数组、位集合（bit set）或者使用整型数据类型（如整型数组、位域等）来表示。在现代编程语言中，也常常提供了专门的位图类或库，如 C++ 中的 std::bitset。

总结起来，位图是一种用于表示和操作位的数据结构，它可以节省存储空间、实现快速的位操作，并在许多领域中有着广泛的应用，包括存储、索引、查询、数据压缩等。

实现位图bitmap

#include <iostream>
#include <vector>
using namespace std;
class Bitmap {
private:std::vector<uint8_t> data; // 位图数据存储uint64_t size; // 位图大小（位数）public:Bitmap(uint64_t bitmapSize) {size = bitmapSize;data.resize((size + 7) / 8, 0); // 位图数据初始化为0}void set(uint64_t index) {if (index >= size) {std::cout << "Index out of range." << std::endl;return;}uint64_t byteIndex = index / 8;uint8_t bitOffset = index % 8;data[byteIndex] |= (1 << bitOffset);}bool test(uint64_t index) {if (index >= size) {std::cout << "Index out of range." << std::endl;return false;}uint64_t byteIndex = index / 8;uint8_t bitOffset = index % 8;return (data[byteIndex] & (1 << bitOffset)) != 0;}
};
int main(){const uint64_t bitmapSize = 28; // 位图大小Bitmap bitmap(bitmapSize); // 创建位图// 设置一些位bitmap.set(0);bitmap.set(5);bitmap.set(10);bitmap.set(15);bitmap.set(18);// 测试位状态for (uint64_t i = 0; i < bitmapSize; i++) {std::cout << "Bit " << i << ": " << bitmap.test(i) << std::endl;}return 0;}

c++提供的bitset

#include <iostream>
#include <bitset>int main() {// 创建一个位图，表示 8 个标志位std::bitset<8> bitmap;// 设置第 2 位和第 5 位为 1bitmap.set(2);bitmap.set(5);// 输出位图的值std::cout << "Bitmap: " << bitmap << std::endl;// 获取第 3 位的值bool bit3 = bitmap.test(3);std::cout << "Bit 3: " << bit3 << std::endl;// 清除第 5 位bitmap.reset(5);// 输出位图的值std::cout << "Bitmap: " << bitmap << std::endl;// 获取位图的大小（位数）size_t size = bitmap.size();std::cout << "Bitmap size: " << size << std::endl;return 0;
}

github链接：https://github.com/mulinhu/CPPer/tree/main/util/bitmap_demo