初识位图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 位为 1
bitmap.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
