BitMap是基于位压缩的布尔数组，核心价值在于用1 bit表示整数存在性，1 GB内存可存85.9亿状态；需绕过STL开销、按uint64_t对齐、手动实现无符号原子操作。
BitMap 本质是布尔数组的位压缩，不是通用容器
BitMap 的核心价值在于用 1 bit 表示一个整数是否存在，1 GB 内存可表示 85.9 亿个 bool 状态（8 × 1024³ bits），远超 std::vector 的实际内存占用（它虽是位压缩，但接口和迭代器行为易引发误用）。真正高效的 BitMap 必须绕过 STL 的抽象开销，直接操作原始内存。
- 不要用
std::vector做海量查重：它的operator[]返回代理对象，循环中频繁调用会拖慢 2–3 倍 - 必须按字长（
uint64_t最常用）对齐分配，避免单 bit 访问的分支判断 - 索引计算公式固定为：
byte_index = n / 8，bit_offset = n % 8；用uint64_t时则为n / 64和n & 63
手动实现 set()/test() 时务必用无符号移位和原子操作
常见错误是用 int 类型做位移，导致右移负数时行为未定义；或在多线程插入场景下忽略并发安全。正确做法是统一使用 uint64_t，并用 &/|= 配合掩码操作。
class BitMap {
uint64_t* data_;
size_t size_bits_;
public:
BitMap(size_t n) : size_bits_(n), data_(new uint64_t[(n + 63) / 64]{}) {}
void set(size_t n) {
if (n >= size_bits_) return;
size_t idx = n / 64;
uint64_t mask = UINT64_C(1) << (n & 63); // 必须用 UINT64_C(1)，不能写 1LL
data_[idx] |= mask;
}
bool test(size_t n) const {
if (n >= size_bits_) return false;
size_t idx = n / 64;
uint64_t mask = UINT64_C(1) << (n & 63);
return (data_[idx] & mask) != 0;
}
};
-
n & 63比n % 64快，且编译器能优化为单条指令 -
UINT64_C(1)确保字面量类型匹配，避免1 在 32 位环境溢出 - 若需线程安全，
data_[idx] |= mask应替换为__atomic_or_fetch(&data_[idx], mask, __ATOMIC_RELAXED)（GCC/Clang）
处理非连续、超大范围整数时，别硬扛——改用 RoaringBitmap 或分段 BitMap
当数据范围是 [0, 1e12) 但实际只插入 1e7 个数，全量分配 125 GB 内存显然不可行。此时 BitMap 失去意义，应切换策略。
- 优先考虑开源库
roaringbitmap：它对稀疏数据自动切分为 16-bit key + bitmap container，内存比朴素 BitMap 低 10–100 倍 - 自行分段需按高 16 位哈希分桶，每桶内用 64KB 小 BitMap（支持 524288 个数），用
std::unordered_map管理> - 千万级以下数据，直接用
std::unordered_set可能更省事——现代 CPU 缓存友好，实测比误用的 BitMap 还快
查重流程中，BitMap 只负责“存在性断言”，不负责去重后排序或计数
BitMap 本身不记录插入次数、顺序或原始值，所有附加需求都得靠外层逻辑补足。例如去重后要输出升序列表，不能指望 BitMap 排序，而应遍历所有 bit 位置收集索引。
立即学习“C++免费学习笔记（深入）”；
- 遍历全部可能值（如 0 到 max_val）做
test(i)是 O(N) 时间，N 是值域大小，不是数据量——这点极易被忽略 - 若原始数据已排序，可在插入时同步写入另一数组，仅追加未出现过的值，避免回扫
- 需要频次统计？BitMap 无能为力，换
std::unordered_map（计数 ≤ 255）或roaring::Roaring64Map
实际部署时，最常被跳过的一步是预估值域上界。没有这个数，BitMap 分配就成盲算——要么爆内存，要么频繁扩容丢数据。
