位图通过位操作高效管理布尔状态，使用std::vector<unsigned int>按位存储，支持set、reset、get操作，适用于去重、排序等场景，空间时间效率优于集合容器。
位图（Bitmap）是一种高效的数据结构，用来表示一组布尔值（0 或 1），常用于快速标记和查询某个元素是否存在。在 C++ 中，可以通过 std::vector<bool> 或手动使用整型数组配合位操作来实现一个简单的位图。下面介绍一种基于位操作的自定义位图实现。
基本原理
位图的核心思想是：用一个 bit 来表示一个整数的状态（比如是否存在）。假设我们要管理 0 到 N-1 的整数，那么只需要 (N + 31) / 32 个 32 位整数（即 unsigned int）即可存储所有状态。
每个 bit 对应一个整数：
- bit[i] = 1 表示整数 i 存在
- bit[i] = 0 表示整数 i 不存在
通过位运算可以高效地进行设置、清除和查询操作。
立即学习“C++免费学习笔记（深入）”；
关键位操作
要实现位图，需要掌握三个基本操作：
- 确定所在整数位置：index / 32 → index >> 5
- 确定在该整数中的 bit 位置：index % 32 → index & 0x1F
- 设置某一位为 1：bits[i >> 5] |= (1U << (i & 0x1F))
- 设置某一位为 0：bits[i >> 5] &= ~(1U << (i & 0x1F))
- 查询某一位是否为 1：(bits[i >> 5] & (1U << (i & 0x1F))) != 0
简单 Bitmap 类实现
#include <iostream>
#include <vector>
class Bitmap {
private:
std::vector<unsigned int> bits;
size_t size;
public:
// 构造函数：指定最大处理的数值范围 [0, n)
Bitmap(size_t n) : size(n) {
bits.resize((n + 31) / 32, 0);
}
// 设置第 i 个位为 1
void set(size_t i) {
if (i >= size) return;
bits[i >> 5] |= (1U << (i & 0x1F));
}
// 将第 i 个位清零
void reset(size_t i) {
if (i >= size) return;
bits[i >> 5] &= ~(1U << (i & 0x1F));
}
// 查询第 i 个位是否为 1
bool get(size_t i) const {
if (i >= size) return false;
return (bits[i >> 5] & (1U << (i & 0x1F))) != 0;
}
// 打印前 n 个位的状态（用于调试）
void print(size_t n) {
for (size_t i = 0; i < n && i < size; ++i) {
std::cout << get(i);
}
std::cout << std::endl;
}
};
使用示例
int main() {
Bitmap bm(64); // 支持 0~63
bm.set(10);
bm.set(20);
bm.set(31);
std::cout << "位状态: ";
bm.print(32); // 输出前32位
std::cout << "get(10): " << bm.get(10) << std::endl; // 1
std::cout << "get(15): " << bm.get(15) << std::endl; // 0
bm.reset(10);
std::cout << "reset 后 get(10): " << bm.get(10) << std::endl; // 0
return 0;
}
这个简单的位图适用于去重、排序（如计数排序变种）、布隆过滤器底层等场景。相比直接使用 std::set 或 std::unordered_set，位图在处理密集整数时空间和时间效率更高。
基本上就这些。理解位操作是关键，实际应用中还可以扩展支持更多功能，比如按位与/或、统计 1 的个数（popcount）等。不复杂但容易忽略边界检查和位运算细节。
