当数据规模达到千万甚至上亿级别时，传统的哈希表去重方案往往面临内存爆炸的问题。比如存储10亿个不重复的整数，如果使用unordered_set，即使只算节点开销也需要几十GB的内存，而位图（Bitmap/Bitset）方案只需要大约125MB就能覆盖整个32位整数空间，空间差距达到两个数量级以上。位图的本质是用一个比特位来标记一个元素是否存在，这种极致压缩的思路使得它在海量数据查重、布隆过滤器底层实现、数据库索引、操作系统页表管理等领域被广泛使用。本文将深入讲解位图的实现原理，并用C++从零手写一个生产级别的Bitset类。
位图的核心原理：一个bit如何代表一个元素
位图的基本思想非常朴素：把一段连续的内存看作一个超长的比特数组，第N个比特位的值（0或1）代表整数N是否存在于集合中。假设我们用uint64_t类型的数组作为底层存储，那么每个元素可以承载64个比特位。要判断整数x是否存在，需要完成两步定位：第一步计算x / 64得到该整数落在数组的第几个元素中，第二步计算x % 64得到它在这个元素内的第几个比特位。
在C++中，除法和取模可以用位运算加速。由于64是2的6次方，x / 64等价于x >> 6，x % 64等价于x & 63。这两种写法在编译器优化后性能完全一致，但显式使用移位能让意图更清晰。置位操作使用按位或：将1左移offset位后与原值相或，即可将目标位设为1而不影响其他位；清零操作使用按位与非；查询则是将原值右移offset位后与1做按位与。这三个基本操作都是O(1)的，并且只涉及一次内存访问和几次位运算。
// 核心位运算示意 size_t idx = x >> 6; // x / 64，定位到数组下标 size_t off = x & 63; // x % 64，定位到位偏移 data[idx] |= (1ULL << off); // 置位：设为1 data[idx] &= ~(1ULL << off); // 清零：设为0 bool exist = (data[idx] >> off) & 1ULL; // 查询：读取该位
需要注意一个常见陷阱：1 << off这种写法在off大于等于31时会溢出，因为字面量1默认是int类型。必须写成1ULL << off，使用unsigned long long字面量才能安全访问一个64位整数的所有位。这是很多初学者实现位图时的第一个bug来源。
手写一个支持动态扩容的C++ Bitset类
标准库的std::bitset虽然高效，但它的长度必须在编译期确定，无法应对运行时才知道范围的场景。实际生产中我们通常需要一个可以动态指定大小、支持自动扩容的位图。下面是一个完整的实现，包含了置位、清零、查询、重置、统计位数等核心接口。
#include <vector>
#include <cstdint>
#include <stdexcept>
class Bitset {
public:
explicit Bitset(size_t nbits)
: bits_((nbits + 63) / 64, 0), nbits_(nbits) {}
void set(size_t pos) {
check(pos);
bits_[pos >> 6] |= (1ULL << (pos & 63));
}
void reset(size_t pos) {
check(pos);
bits_[pos >> 6] &= ~(1ULL << (pos & 63));
}
bool test(size_t pos) const {
check(pos);
return (bits_[pos >> 6] >> (pos & 63)) & 1ULL;
}
// 统计所有为1的位数（popcount）
size_t count() const {
size_t n = 0;
for (uint64_t v : bits_) n += __builtin_popcountll(v);
return n;
}
void clear() {
std::fill(bits_.begin(), bits_.end(), 0);
}
size_t size() const { return nbits_; }
private:
void check(size_t pos) const {
if (pos >= nbits_) throw std::out_of_range("Bitset: out of range");
}
std::vector<uint64_t> bits_;
size_t nbits_;
};
这个实现有几个值得展开的细节。首先是构造函数中(nbits + 63) / 64的写法，这是经典的向上取整技巧，确保即使nbits不是64的整数倍也能分配足够的存储。其次是count函数中使用的__builtin_popcountll，这是GCC和Clang提供的内建函数，会被编译成单条POPCNT指令，比手动循环统计每一位快几十倍。MSVC下对应的函数是__popcnt64，如果追求跨平台可以条件编译处理。
从性能角度看，check函数中的边界检查在某些极端性能敏感的场景下可以去掉，改为文档约定调用者保证合法性。但生产代码建议保留，因为越界写一个uint64_t数组破坏的是相邻64个比特的数据，这种bug排查起来极其痛苦。空间占用方面，这个Bitset存储N个标志只需要约N/8字节，10亿个标志约120MB，而用vector<bool>虽然理论上也做了位压缩，但它的代理引用设计在多线程和高性能场景下有著名的坑，不推荐使用。
性能优化：缓存友好与批量操作
位图天生是缓存友好的数据结构。一次读取64位就能覆盖64个连续整数的查询，CPU缓存行通常为64字节，正好对应512个比特位。当业务中需要遍历位图统计或查找时，应尽量按uint64_t为单位批量处理，而不是逐位调用test函数。比如查找第一个为1的位，可以先用__builtin_ctzll（统计尾部零的个数）快速定位非零元素中的目标位，遇到零元素直接跳过，整体速度可以提升一个数量级。
// 查找第一个为1的位，未找到返回npos
size_t first_set(const std::vector<uint64_t>& bits) {
for (size_t i = 0; i < bits.size(); ++i) {
if (bits[i] != 0) {
return i * 64 + __builtin_ctzll(bits[i]);
}
}
return SIZE_MAX; // npos
}
另一个优化方向是多线程写入。如果不同的线程操作的区域落在同一个uint64_t内，普通的按位或操作会产生数据竞争。解决方案有两种：一是按业务预先划分区间，保证线程之间不共享机器字；二是使用C++11引入的std::atomic<uint64_t>配合fetch_or做原子的按位或操作，代价是会有一定的性能损耗。在日志去重、爬虫URL过滤这类高并发写入场景中，原子位图是非常常见的架构组件。
此外，当数据不是稠密分布的整数而是字符串时，可以先对元素做哈希映射到整数再存入位图，但哈希冲突会导致误判。如果业务能容忍小概率的误判率，可以升级为布隆过滤器，即用多个独立哈希函数在位图中置多个位，查询时所有位都为1才判定存在。布隆过滤器正是以位图为底层存储的，掌握了位图实现，再理解布隆过滤器就水到渠成。
实战案例：大文件整数查重
最后通过一个典型场景串联以上知识：给定一个包含1亿个随机整数（范围0到10亿）的大文件，要求找出其中出现过的所有不重复整数。使用位图的方案非常直接：申请一个覆盖10亿范围的Bitset，约为125MB内存，顺序读取文件，每读到一个整数就调用set置位，最后遍历位图中所有为1的位输出即可。整个算法的时间复杂度为O(N + N/64)，内存占用只有哈希表方案的几十分之一。
#include <cstdio>
int main() {
const size_t RANGE = 1000000000ULL;
Bitset bs(RANGE);
FILE* fp = fopen("data.txt", "r");
long long x;
while (fscanf(fp, "%lld", &x) == 1) {
bs.set((size_t)x);
}
fclose(fp);
// 遍历输出所有出现过的整数
for (size_t i = 0; i < bs.size(); ++i) {
if (bs.test(i)) printf("%lld\n", (long long)i);
}
return 0;
}
这个案例还可以进一步扩展：如果要统计出现两次以上的整数，可以升级为两位表示一个元素计数，或者用两个位图叠加；如果文件大到单机内存放不下，可以按整数高位分段做多趟处理，这也是经典的分治位图思路，在面试中出现的频率非常高。位图看似简单，但它背后的空间换时间和位运算优化思想，是衡量C++工程师基本功的一块试金石，值得彻底吃透。
C++ Bitset位图算法海量数据查重修改时间：2026-09-02 09:08:45