位图通过二进制位高效表示元素存在状态，使用位运算实现快速操作，相比布尔数组节省32~64倍内存，适用于去重统计、布隆过滤器、内存管理等场景。
在处理海量数据集合时，内存效率和操作速度至关重要。C++中实现一个位图（BitSet）是一种非常高效的方式，利用位运算可以直接对单个比特进行操作，从而大幅节省内存并提升性能。下面介绍如何从零实现一个简单的位图结构，并说明其核心原理与应用场景。
位图的基本原理
位图使用一个二进制位来表示一个元素的存在状态（0 表示不存在，1 表示存在）。假设要表示区间 [0, n) 内的整数集合，只需要 n 个比特即可。相比使用布尔数组或哈希集合，位图在空间上具有极大优势——理论上可节省 32~64 倍内存（取决于机器字长）。
例如：表示 100 万个整数的存在性，用 bool 数组需要约 1MB，而用位图仅需约 125KB。
核心数据结构与位运算操作
我们使用 unsigned int 或 unsigned long long 
类型的数组作为底层存储，每个元素称为“字”（word），每个字管理多个比特。
关键在于通过位运算快速定位和修改某一位：
- 确定所在字的位置：index / bits_per_word
- 确定在字内的偏移：index % bits_per_word
- 设置某位为1：data[word_index] |= (1U
- 设置某位为0：data[word_index] &= ~(1U
- 查询某位是否为1：(data[word_index] & (1U
注意：位移操作应确保不越界，且使用无符号类型避免未定义行为。
简易 BitSet 实现示例
以下是一个轻量级的 BitSet 类实现：
class BitSet {
private:
unsigned int* data;
size_t size_in_bits;
static const size_t BITS_PER_WORD = 32;
public:
BitSet(size_t n) : size_in_bits(n) {
size_t num_words = (n + BITS_PER_WORD - 1) / BITS_PER_WORD;
data = new unsigned int[num_words]{};
}
~BitSet() {
delete[] data;
}
void set(size_t index) {
if (index >= size_in_bits) return;
size_t word = index / BITS_PER_WORD;
size_t bit = index % BITS_PER_WORD;
data[word] |= (1U zuojiankuohaophpcnzuojiankuohaophpcn bit);
}
void reset(size_t index) {
if (index >= size_in_bits) return;
size_t word = index / BITS_PER_WORD;
size_t bit = index % BITS_PER_WORD;
data[word] &= ~(1U zuojiankuohaophpcnzuojiankuohaophpcn bit);
}
bool test(size_t index) const {
if (index >= size_in_bits) return false;
size_t word = index / BITS_PER_WORD;
size_t bit = index % BITS_PER_WORD;
return (data[word] & (1U zuojiankuohaophpcnzuojiankuohaophpcn bit)) != 0;
}};
使用方式简单直观：
BitSet bs(1000); // 支持 0~999
bs.set(10);
bs.set(500);
if (bs.test(10)) {
// 执行逻辑
}
典型应用场景
位图特别适合以下场景：
-
去重统计：如日活跃用户标记，ID 范围已知时可用 BitSet 高效记录
-
布隆过滤器底层结构：配合哈希函数实现概率性判断
-
内存池管理：操作系统或自定义分配器中标记块是否空闲
-
排序与查找优化：对小范围整数排序，遍历 BitSet 即可输出有序序列
基本上就这些。掌握位图不仅提升对位运算的理解，也增强了处理大数据集时的空间优化能力。实际项目中也可直接使用 std::bitset（固定大小）或 std::vector
