位图排序要求数据不能重复，因为其本质是布尔映射，每个bit仅表示“存在”或“不存在”，重复值会导致频次信息丢失，输出隐式去重。
位图排序不是万能的，但它在特定约束下（无重复、值域已知、内存极紧）是唯一可行的线性时间方案。如果你的数据不满足“所有整数 ∈ [0, N) 且互异”，直接用 std::sort 更安全。
为什么位图排序要求数据不能重复
位图本质是布尔映射：每个 bit 只能存 0 或 1，代表“不存在”或“存在”。一旦输入含重复值，比如两次写入 set(42)，第二次操作不会报错，但也不会改变状态——你丢失了频次信息，更无法还原原始序列。排序结果看似正确，实则隐式去重，与原意不符。
- 错误现象：
bitmap_sort({5, 5, 3})输出{3, 5}，而非{3, 5, 5} - 使用场景：日志去重统计、IP 黑白名单判定、整数集合归并
- 若需保留重复，必须改用计数位图（每个元素占多个 bit）或退回到
std::unordered_map<int int></int>
set() 和 test() 的位运算细节必须对齐
核心是三组常量必须一致：WORD == 32、SHIFT == 5、MASK == 0x1f。它们共同定义“每 32 个数打包进一个 uint32_t”，任何一项错配都会导致位偏移错乱。
- 常见错误：
i % 32写成i & 0x1f没问题，但若数组类型是uint64_t却仍用SHIFT == 5，就会只覆盖低 32 位 - 推荐写法统一用位运算：
bits[i >> 5] |= (1U ，避免除法和取模开销 - 注意
1U而非1：防止左移超过 31 位时发生符号扩展未定义行为
内存边界检查不能只靠 size 成员变量
构造时传入的 n 是逻辑容量（最大可表示整数），但实际分配的 bits 容量是 (n + 31) / 32 个 uint32_t。如果调用 set(n)，索引 n / 32 可能越界——因为 n 本身是上界，合法最大索引是 n - 1。
- 典型 crash：
Bitmap bm(100); bm.set(100);→ 访问bits[3]（越界） - 修复方式：在
set()、get()中加判断if (i >= size) return;，且size应为最大允许索引 + 1 - 更稳妥做法：用
std::vector<uint32_t>::at()</uint32_t>替代[]，触发边界异常（仅调试期）
位图排序的输出循环必须遍历整个值域，不是输入长度
排序结果由值域密度决定，不是输入个数。例如输入只有 3 个数 {1, 9999999, 0}，你也得从 i = 0 扫到 i = MAX_VALUE - 1 才能保证不漏掉中间那个 9999999。
- 性能陷阱：若值域极大（如
MAX_VALUE == 2^31）但数据稀疏，遍历耗时远超输入规模 - 兼容性影响：32 位系统上
MAX_VALUE > 2^31会导致int溢出，应统一用size_t或uint64_t - 真实项目中，建议把值域上限作为模板参数（
BitmapSort），编译期校验
真正难的不是写对那几行位操作，而是确认你的业务是否真的满足“无重复+值域可控+内存卡死”这三重前提。漏掉任意一条，位图排序就从银弹变成定时炸弹。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
