位图用位存储布尔状态，C++中通过位运算高效实现，以字节数组为底层存储，每bit代表一个整数是否存在，支持set、clear、test操作，节省内存至N/8字节。
位图（Bitmap）是一种用单个位来存储信息的数据结构，适合处理大量布尔状态的场景，比如去重、排序、布隆过滤器等。C++中通过位运算和空间优化可以高效实现一个轻量级的 Bitmap。
基本原理与设计思路
一个 bit 可以表示 0 或 1 状态，如果我们想记录 N 个整数是否存在，传统数组需要 N 字节，而位图只需 N/8 字节（向下取整并加一），大幅节省内存。
核心思想是：用一个字节数组（或整型数组）作为底层存储，每个 bit 代表一个整数是否出现过。例如第 i 个 bit 为 1 表示整数 i 存在。
关键操作：
立即学习“C++免费学习笔记（深入）”；
- set(i)：将第 i 位置 1
- clear(i)：将第 i 位置 0
- test(i)：查询第 i 位是否为 1
位运算实现细节
使用位运算对指定位置进行操作。假设我们有一个 unsigned char 数组，要操作第 i 位：
- 确定该位所在的字节下标：i / 8 或 i >> 3
- 确定在字节内的偏移量：i % 8 或 i & 7
- 设置某一位：使用按位或 |= (1
- 清除某一位：使用按位与 &= ~(1
- 测试某一位：使用按位与判断结果是否非零
代码示例：
class Bitmap {
private:
std::vector<unsigned char> data;
size_t n_bits;
<p>public:
explicit Bitmap(size_t bits) : n_bits(bits) {
data.resize((bits + 7) / 8, 0); // 向上取整
}</p><pre class="brush:php;toolbar:false;">void set(size_t i) {
if (i >= n_bits) return;
size_t byte_idx = i >> 3;
size_t offset = i & 7;
data[byte_idx] |= (1U << offset);
}
void clear(size_t i) {
if (i >= n_bits) return;
size_t byte_idx = i >> 3;
size_t offset = i & 7;
data[byte_idx] &= ~(1U << offset);
}
bool test(size_t i) const {
if (i >= n_bits) return false;
size_t byte_idx = i >> 3;
size_t offset = i & 7;
return (data[byte_idx] & (1U << offset)) != 0;
}};
空间优化技巧
为了进一步提升性能和减少内存占用，可以考虑以下几点：
- 使用 uint32_t 或 uint64_t 替代 unsigned char 数组，减少边界检查次数，提高缓存命中率
- 采用模板参数指定元素类型，实现通用性
- 预分配足够空间避免频繁扩容
- 批量操作时可用“平行位”技术或内置函数如 __builtin_popcount 统计 1 的个数
进阶版使用 uint32_t 数组的例子：
template<typename Block = uint32_t>
class FastBitmap {
static constexpr int BITS_PER_BLOCK = sizeof(Block) * 8;
std::vector<Block> data;
size_t n_bits;
<p>public:
explicit FastBitmap(size_t bits) : n_bits(bits) {
data.resize((bits + BITS_PER_BLOCK - 1) / BITS_PER_BLOCK, 0);
}</p><pre class="brush:php;toolbar:false;">void set(size_t i) {
if (i >= n_bits) return;
size_t block = i / BITS_PER_BLOCK;
size_t offset = i % BITS_PER_BLOCK;
data[block] |= (Block(1) << offset);
}
bool test(size_t i) const {
if (i >= n_bits) return false;
size_t block = i / BITS_PER_BLOCK;
size_t offset = i % BITS_PER_BLOCK;
return (data[block] & (Block(1) << offset)) != 0;
}
void clear(size_t i) {
if (i >= n_bits) return;
size_t block = i / BITS_PER_BLOCK;
size_t offset = i % BITS_PER_BLOCK;
data[block] &= ~(Block(1) << offset);
}};
应用场景与注意事项
Bitmap 常用于：
- 快速去重（如统计 1~100 万中出现过的数字）
- 内存敏感的索引结构
- 配合哈希实现布隆过滤器
- 操作系统中的页分配管理
注意点：
- 只适用于整数范围有限的场景（比如 0~几千万）
- 不支持负数（除非做偏移映射）
- 稀疏数据可能浪费空间，此时可考虑 Roaring Bitmap
- 线程安全需外部保证，必要时加锁或使用原子操作
基本上就这些。掌握位运算和内存布局，就能写出高效简洁的位图实现。
