悠悠楠杉
网站页面
C++实现位图（Bitmap）数据结构：位运算与空间优化的高效实践
12/01
![]()
在处理海量数据时，我们常常需要记录某些元素是否存在或是否被访问过。如果使用传统的布尔数组（bool[]），每个元素将占用至少1字节（8位），即使它的值只是true或false。当数据规模达到百万甚至亿级时，这种存储方式会带来巨大的内存开销。这时，位图（Bitmap） 就成为一种极具优势的数据结构——它利用每一个比特（bit）来表示一个状态，从而将空间消耗降低为原来的1/8。
位图的核心思想是：用一个二进制位表示一个整数的存在与否。例如，若想表示数字i是否出现过，只需将第i位设置为1。由于C++中没有直接按位寻址的语法，我们需要借助位运算和字节数组来手动实现这一机制。
首先定义位图的基本结构：
cpp
class Bitmap {
private:
unsigned char* data; // 存储位图的字节数组
sizet numbits; // 总位数
sizet numbytes; // 所需字节数（向上取整）
public:
explicit Bitmap(sizet n) : numbits(n) {
num_bytes = (n + 7) / 8; // 向上取整除以8
data = new unsigned charnum_bytes; // 初始化为0
}
~Bitmap() {
delete[] data;
}
};
接下来是关键操作：设置某一位为1 和 查询某一位是否为1。这需要用到基本的位运算技巧。
要定位第i个位，首先要确定它位于哪个字节中，即 i / 8，也就是 i >> 3；然后确定它在该字节中的偏移量，即 i % 8，也就是 i & 7。
设置第i位的代码如下：
cpp
void set(size_t i) {
if (i >= num_bits) return;
size_t byte_idx = i >> 3;
size_t bit_idx = i & 7;
data[byte_idx] |= (1 << bit_idx);
}
这里使用了左移操作 (1 << bit_idx) 构造出只有一位为1的掩码，再通过按位或 |= 将目标位置1。
判断第i位是否为1则使用按位与：
cpp
bool get(size_t i) const {
if (i >= num_bits) return false;
size_t byte_idx = i >> 3;
size_t bit_idx = i & 7;
return (data[byte_idx] & (1 << bit_idx)) != 0;
}
这两个操作的时间复杂度均为 O(1)，且不涉及任何动态内存分配，效率极高。
为了进一步提升实用性，我们可以添加清除操作：
cpp
void clear(size_t i) {
if (i >= num_bits) return;
size_t byte_idx = i >> 3;
size_t bit_idx = i & 7;
data[byte_idx] &= ~(1 << bit_idx);
}
使用按位取反 ~ 构造出除目标位外全为1的掩码，再进行按位与，即可将指定位置0。
在整个实现过程中，我们始终关注空间利用率。相比 std::vector<bool>，虽然标准库也做了位压缩，但其接口抽象可能带来性能损耗，且行为不符合常规容器语义（返回的是代理对象而非引用）。而手动实现的位图完全可控，适合嵌入式系统、高频交易、布隆过滤器底层等对性能敏感的场景。
此外，还可以通过模板参数支持不同大小的基础类型（如使用 uint32_t 或 uint64_t 数组代替 unsigned char），在支持宽寄存器的平台上进一步加速批量操作，比如使用“查表法”或SIMD指令进行快速扫描。
总结来说，位图的本质是用计算换空间。通过精巧的位运算，我们将原本需要 N 字节的空间压缩到 N/8 字节，代价只是每次访问多几个简单的移位和掩码操作。在C++中实现这样一个结构，不仅加深了对内存布局和位操作的理解，也为解决实际工程问题提供了轻量高效的工具。
