位图排序适合海量整数去重与排序，因其在值域远小于数据量时空间效率极高（如1亿个[0,100万)整数仅需125KB），但要求值域已知且紧凑，否则退化为稀疏哈希表；手写uint64_t位图可避免std::vector代理对象问题，通过i>>6和i&63加速寻址，并需边界检查；排序本质是顺序扫描位图输出置位下标，时间复杂度O(N)取决于值域上限而非数据量，负数需偏移处理，I/O应分块读写以控内存，性能瓶颈常在缓存访问模式，可用__builtin_popcountll等优化位扫描。
位图排序为什么适合海量整数去重与排序
位图排序不是万能的，它只在数据范围远小于数据量时才真正省空间。比如对 1 亿个 [0, 1000000) 范围内的整数排序，用 std::vector<bool></bool> 或手动管理的 uint64_t 数组只需约 125KB 内存；而直接存 1 亿个 int 就要 400MB —— 差三个数量级。关键前提是：值域必须已知且紧凑，否则位图退化成稀疏哈希表，反而更费内存。
常见误用场景：std::vector<bool></bool> 被当成普通容器调用 .data()（它不保证连续存储）、用 char 数组但未按位寻址（浪费 8 倍空间）、忽略负数或偏移导致越界访问。
如何手写紧凑位图并支持快速 set/get
别依赖 std::vector<bool></bool> 的“位压缩”语义——它的迭代器行为和内存布局不可移植，且 operator[] 返回代理对象，无法取地址。稳妥做法是自己封装一个基于 uint64_t 的位图类：
class BitMap {
std::vector<uint64_t> bits;
size_t size_;
public:
BitMap(size_t max_val) : size_(max_val + 1), bits((max_val + 64) / 64) {}
void set(size_t i) { bits[i / 64] |= (1ULL << (i % 64)); }
bool get(size_t i) const { return i < size_ && (bits[i / 64] & (1ULL << (i % 64))); }
};
-
i / 64和i % 64是关键，用位运算替代除法模运算可提速（i >> 6、i & 63） - 构造时按需分配
uint64_t数量，避免std::vector<bool></bool>的隐式扩容开销 - 务必检查
i < size_，否则get()对超界索引返回垃圾值而非报错
位图排序的完整流程与 I/O 边界处理
位图本身不排序，它只记录存在性；真正的“排序输出”是顺序扫描位图、遇到置位就输出下标。这个过程是 O(N)，N 是值域大小，不是输入数据量——所以值域不能过大。
立即学习“C++免费学习笔记（深入）”；
实操中容易卡住的点：
- 输入含负数？统一加偏移量（如最小值的绝对值），并在输出时减回，
offset必须参与所有set()和get()计算 - 数据来自文件流？别一次性读完再建图，用
std::istream::read()分块读整数，边读边set()，降低峰值内存 - 输出到文件？用
std::ofstream配合<<会慢，改用write()写二进制格式，或至少关闭同步：std::ios::sync_with_stdio(false)
性能瓶颈常不在位操作，而在内存访问模式
当值域达到千万级，uint64_t 数组可能跨多个 cache line，顺序扫描时 CPU 预取效率下降。实测发现：对 1000 万位的位图，用 __builtin_popcountll() 逐 uint64_t 统计并定位置位位置，比单 bit 扫描快 3–5 倍。
优化建议：
- 对每个
uint64_t元素，先用if (word == 0) continue;跳过全零块 - 用
__builtin_ctzll(word)找最低位 1，循环清除最低位（word &= word - 1），避免模 64 运算 - 若目标平台支持 AVX2，可用
_mm256_movemask_epi8并行查 32 字节中的非零字节，但需额外处理字节内位
位图排序的“海量”是相对的——它把时间换空间，把排序复杂度从 O(n log n) 换成 O(N)，但 N 是值域上限。一旦值域失控，缓存失效、内存带宽吃紧，优势立刻反转。真正难的不是写对位操作，而是提前判断数据分布是否匹配位图前提。
