位图（BitSet）是一种用比特位来表示数据存在状态的数据结构，每个比特位对应一个数据值，1表示数据存在，0表示不存在。在处理海量整数去重、判断元素是否存在等场景时，位图的内存占用远低于普通数组或哈希表，是C++中优化性能的重要手段。
位图的核心原理
位图的核心思想是利用位运算的特性，将整数范围映射到连续的比特位序列中。假设要处理的数据范围是0到N，那么只需要N+1个比特位即可，换算成字节的话只需要(N+1)/8个字节的存储空间。例如要处理0到1000000的整数，普通数组需要至少4MB（假设用int存储），而位图只需要约125KB，内存优势非常明显。
位图的基础操作包括设置某一位为1、清除某一位为0、判断某一位是否为1，这些操作都可以通过位运算快速完成。常用的位运算包括左移<<、右移>>、按位或|、按位与&、按位取反~。
C++实现位图的核心步骤
1. 底层存储设计
位图的底层存储通常使用unsigned char数组或者std::vector<unsigned char>，因为unsigned char占1个字节，方便按字节操作。我们需要根据要支持的最大数据值计算需要的字节数：
#include <vector>
#include <cstddef>
class BitSet {
private:
std::vector<unsigned char> data; // 存储比特位的数组
size_t bitSize; // 位图支持的最大比特位数量
public:
// 构造函数，传入支持的最大数值，即比特位数量
explicit BitSet(size_t maxNum) : bitSize(maxNum + 1) {
// 计算需要的字节数，每个unsigned char存8位，不足1字节按1字节算
size_t byteSize = (bitSize + 7) / 8;
data.resize(byteSize, 0); // 初始化所有位为0
}
};
2. 封装位操作函数
接下来需要实现三个核心操作：设置位、清除位、判断位状态。假设要操作数值为num的位，首先需要计算num对应的字节索引和字节内的比特位索引：
- 字节索引 = num / 8，即num右移3位
- 比特位索引 = num % 8，即num和7做按位与运算
具体实现如下：
public:
// 设置第num位为1
void set(size_t num) {
if (num >= bitSize) return; // 超出范围直接返回
size_t byteIndex = num / 8;
size_t bitIndex = num % 8;
// 对应字节的第bitIndex位设为1，其他位不变
data[byteIndex] |= (1 << bitIndex);
}
// 清除第num位为0
void reset(size_t num) {
if (num >= bitSize) return;
size_t byteIndex = num / 8;
size_t bitIndex = num % 8;
// 对应字节的第bitIndex位设为0，其他位不变
data[byteIndex] &= ~(1 << bitIndex);
}
// 判断第num位是否为1
bool test(size_t num) const {
if (num >= bitSize) return false;
size_t byteIndex = num / 8;
size_t bitIndex = num % 8;
// 判断对应位是否为1
return (data[byteIndex] & (1 << bitIndex)) != 0;
}
3. 扩展常用功能
根据需求可以扩展更多功能，比如获取位图中所有被设置的位、清空整个位图、获取位图的大小等：
public:
// 清空所有位，全部设为0
void clear() {
std::fill(data.begin(), data.end(), 0);
}
// 获取位图支持的最大数值
size_t getMaxNum() const {
return bitSize - 1;
}
// 获取所有被设置的数值
std::vector<size_t> getAllSetNums() const {
std::vector<size_t> result;
for (size_t i = 0; i < bitSize; ++i) {
if (test(i)) {
result.push_back(i);
}
}
return result;
}
};
位图处理海量数据的示例
假设现在有一个场景：有10亿个不重复的整数，范围在0到100000000之间，需要快速判断某个数是否存在，同时统计所有存在的数。使用我们实现的BitSet可以轻松完成：
#include <iostream>
#include <cstdlib>
#include <ctime>
int main() {
// 初始化随机数种子
std::srand(std::time(nullptr));
// 创建支持0到1亿的位图
BitSet bitSet(100000000);
// 模拟插入1000个随机数据
for (int i = 0; i < 1000; ++i) {
size_t num = std::rand() % 100000001;
bitSet.set(num);
}
// 判断某个数是否存在
size_t target = 1234567;
if (bitSet.test(target)) {
std::cout << target << " 存在于数据集合中" << std::endl;
} else {
std::cout << target << " 不存在于数据集合中" << std::endl;
}
// 获取所有存在的数（这里仅示例，实际10亿数据不建议全部遍历输出）
// auto allNums = bitSet.getAllSetNums();
// std::cout << "存在的数的数量：" << allNums.size() << std::endl;
return 0;
}
位图的适用场景和注意事项
位图非常适合处理整数类型的海量数据去重、存在性判断、求交集并集等场景，但需要注意以下几点：
- 位图只能处理整数类型的数据，非整数数据需要先映射到整数范围才能使用
- 如果数据范围非常大且稀疏（即存在的数很少），位图的内存优势会减弱，此时可以考虑使用稀疏位图或者布隆过滤器
- 实现时要注意数值范围的检查，避免数组越界访问
- 位运算操作要注意符号问题，尽量使用无符号类型进行计算，避免移位时出现未定义行为
通过上述实现，我们可以在C++中快速搭建一个可用的位图结构，利用位运算的高效特性处理海量数据集合，大幅提升程序的性能和内存利用率。