题目
10 亿个无序整数，内存有限（比如 1 GB），要求
排序去重后输出。如果只问个数，就是
统计 distinct 个数。追问：如果还想知道哪些数重复了、哪些只出现一次，怎么办？
这就是位图（BitMap）的主场。这道题在面试里出现的频率极高，因为它考的不是某个精巧算法，而是一个思维转换：
当整数有界时，「值域」本身就可以当存储用。
一、核心洞察：用「值域」换「空间」
先算账。10 亿个 32 位整数，原样放进内存：
一般的机器直接出局。换
HashSet？每个元素要装装箱后的对象、引用和哈希节点，一个元素几十字节，10 亿个就是
几十 GB，比原数组还夸张。
但注意一件事：
这些整数的值域是有界的。如果值域是
0 ~ 10^9 - 1，那一共只有 10^9 种可能的取值 —— 给每种取值发一个「来过 / 没来」的记号，只需要：
10^9 bit = 10^9 / 8 = 125,000,000 字节 ≈ 119 MiB
119 MiB，1 GB 的内存限制轻轻松松装下，还顺带解决了去重和排序：
- 去重是白送的：一个 bit 只能置 1 一次，重复的数再来，那一位已经是 1 了；
- 排序也是白送的：最后按 bit 下标从小到大扫一遍，输出天然有序。
这就是全部魔法：
数据量决定你要处理多少个输入，值域决定位图要开多大。 当值域远小于「数据量 × 每个数据的字节数 × 8」时，位图就是降维打击 —— 这里压缩比是 32 : 1。
一句话总结：位图不是一种排序算法，是一种「用值域大小换数据量空间」的存储决策。 排序和去重只是它的副产品。
二、基础版：1-bit 位图，去重和排序都是白送
class BitMap:
def __init__(self, size: int):
self.size = size
# 每 32 个整数挤进一个 32 位字
self.words = [0] * ((size + 31) // 32)
def add(self, v: int) -> None:
# 置位：只翻 v 对应的那 1 bit，同字其他位原样不动
self.words[v >> 5] |= 1 << (v & 31)
def contains(self, v: int) -> bool:
return (self.words[v >> 5] >> (v & 31)) & 1 == 1
def sorted_distinct(self) -> list[int]:
# 按 bit 下标从小到大扫，输出即有序去重序列
return [v for v in range(self.size) if self.contains(v)]
三步走：
置位（
|=）、
判重（看一眼 bit 是 0 还是 1）、
扫描（下标顺序就是值顺序）。整道题的主体就这三行。
用一组小数据走一遍 ——
[37, 12, 37, 5, 63, 42]，值域
0 ~ 63（刚好两个字）：
注意第二个 37：
locate 帧算出它落在字 1 第 5 位，那一位已经是 1 —— 直接跳过，
去重就这样发生了，没有比较、没有哈希、没有额外空间。
三、动画怎么看
动画一（[37, 12, 37, 5, 63, 42]，14 帧） 演示 1-bit 位图全流程。每个输入数占两帧：
locate 帧算
word 和
bit（
37 = 1 × 32 + 5，所以是字 1 第 5 位），
act 帧执行置位或跳过。画面分五段：
- 横幅：当前阶段（定位 / 置位 / 跳过 / 扫描输出）和关键数值；
- 位图阵列：2 行 × 32 列，一行一个字，绿 = 已置位、橙 = 当前位、金 = 命中重复，行首标 word 号、行下标 bit 刻度；
- 定位等式：
v = word × 32 + bit，置位帧额外显示指令 words[w] |= 1 << b；
- 输出 chips：已置位的值，升序排列，最新置位的烫金；
- 进度判定：已置位 / 已跳过 / 共多少输入。
值得盯的是第 5、6 帧（第二个 37）：
locate 帧就发现那一位已是 1，
act 帧什么都不做 —— 去重发生在「看一眼」里。
动画二（[3, 7, 3, 3, 12, 7]，8 帧） 演示 2-bit 位图，回答三个问题：出现过哪些、哪些重复了、哪些只出现一次。
四、完整推演表
主例
[37, 12, 37, 5, 63, 42]，值域
0 ~ 63：
扫描输出：
5、12、37、42、63 —— 6 个输入去重后 5 个，天然升序。
换成 10 亿规模，账本是这样的：
注意最后两行：如果值的分布不可控（可能有负数、可能是整个 int32 范围），直接按
2^32 开全域位图 —— 512 MiB 换一个不用操心偏移的干净实现，这笔账大多数时候都划算。
五、2-bit 位图：去重、数重复、找唯一
1-bit 位图只有一个答案维度：「出现过 / 没出现过」。想同时知道
哪些数重复了、哪些只出现一次，给每个数加一个 bit：
00 未出现 → 01 出现一次 → 10 出现多次 → （11 保留态）
转移表：
def add(self, v: int) -> None:
cur = self._state(v)
if cur == 0b00:
self._set(v, 0b01) # 一次
elif cur == 0b01:
self._set(v, 0b10) # 升级成多次
elif cur == 0b11:
self._set(v, 0b10) # 保留态兜底
# cur == 0b10：已经是多次，什么都不做
为什么不是「00/01/10/11 分别表示出现 0/1/2/3 次」？那样第 4 次就溢出了，而这道题只需要区分「一次」和「多次」两档 ——
10 就是多次的垃圾桶，来多少都接得住。
空间代价是 1-bit 位图的两倍：int32 全域 2-bit 位图 1 GiB。换来的是一次扫描同时输出三个集合：
六、位运算三件套与内存布局
三个动作，每个都对应一条位运算，值得逐字记：
定位：word = v >> 5 （v 落在第几个字，每字 32 个数）
bit = v & 31 （v 是字内第几位）
置位：words[word] |= 1 << bit
查存：(words[word] >> bit) & 1 == 1
清位：words[word] &= ~(1 << bit) ← 波浪号不能丢
以 37 为例：
37 >> 5 = 1（在字 1），
37 & 31 = 5（字内第 5 位）—— 因为
37 = 1 × 32 + 5。字内 32 个 bit 互不干扰，
|= 只翻本位，这是整套操作安全性的根基。
几个工程细节：
- 负数要减 min 平移：
idx = v - min。不减就是负下标，直接越界；
- 字节序无关：位图按「值」寻址，不按内存布局寻址，大小端机器上行为一致；
- 字长是平台细节：演示用 32 位字（对应 int32），工程上可以用 64 位字（每字 64 个数，
>> 6 / & 63），寻址更粗、缓存更友好；
- 扫描可以按字加速：整字是 0 就跳过 32 位，统计 distinct 个数用 popcount（
Integer.bitCount）一次算一整个字，比逐位判存快 32 倍。
七、变体：值域爆炸怎么办
位图的前提是
值域有界且不大。这个前提不成立时，套路是降维 + 分块：
64 位随机数 / UUID：值域
2^64，位图要
2^64 bit = 2 EiB，银河系都装不下。这时候：
- 范围分桶：先按高位把数据切到若干桶（落磁盘），每个桶的值域缩小到能开位图，桶内位图去重，桶间按序归并；
- 哈希分区：值域不好切就按哈希分，代价是丢掉了「天然有序」，归并时要重新排；
- 布隆过滤器：只回答「可能在 / 一定不在」，有假阳性、不能去重输出，但空间是位图的又一个数量级之下；
- 外排：终极方案，内存只留缓冲区分块排序，结果落磁盘归并 —— 这就是「大数据量排序」的标准答案，位图是它的有界值域特例。
多机版：按值域切片把数据分到不同机器（range sharding），每台机器独立位图，最后按片序拼接 —— 去重和排序在分片界面上天然成立。
只要 distinct 个数：扫完位图后
Integer.bitCount 逐字累加，不需要输出序列，
O(值域 / 32) 个字操作。
八、复杂度与选型
O(n + 值域) 里的两个项要分开看：
n 是数据量，值域是值域。10 亿个数、值域 10^9，两项同阶，总共约 2×10^9 次基本操作；而比较排序是
10^9 × log2(10^9) ≈ 10^9 × 30，差了 15 倍，而且排序的常数（比较、交换、缓存不友好）远大于位图的置位。
选型的关键比值是
值域 / 数据量：
- 值域 ≈ 数据量 × 32（int32 有界）→ 位图完胜，32 : 1 压缩；
- 值域 >> 数据量（比如 100 个数散在
2^32 里）→ 位图巨亏，512 MiB 存 100 个数，老老实实用 HashSet；
- 值域 >> 数据量 × 32（64 位场景）→ 位图直接出局，走向分块或外排。
九、常见坑：五个每一个都真实致命
9.1 置位写成赋值：|= 变 =
words[v >> 5] = 1 << (v & 31) # 错，应为 |=
赋值把
整个字冲掉，同字其他位置的全部清零。反例
[0, 5]：先置 0，再置 5，0 被冲掉 —— 输出只剩
[5]。这类 bug 在稀疏数据上要漏掉一大片。
9.2 清位忘写波浪号
words[w] &= (1 << b) # 错，应为 &= ~(1 << b)
& 之后整个字只剩本位，同字其他位被误伤。反例：字里已有 0 和 5，清 5 会把 0 一起清掉。
~ 一丢，清位变屠版。
9.3 负数不减 min
负数值直接当
idx = v 用就是负下标，越界。正确做法
idx = v - min，位图大小 =
max - min + 1。面试题经常 silently 假设「非负整数」，主动问一句「值域是多少、有没有负数」是加分项。
9.4 没评估值域就上位图
64 位整数、UUID、手机号（11 位十进制 ≈ 2^37）看着都不大，一算全傻眼：手机号值域
10^11，位图要
10^11 bit ≈ 11.6 GiB，比原数据（10 亿 × 8 字节 = 8 GB）还大。
先算值域账，再决定用不用位图。
9.5 1-bit 位图答不了「出现几次」
「找只出现一次的数」在 1-bit 位图里无解 —— 出现过两次和一次，bit 都是 1。这个需求必须上加一个 bit（2-bit 位图）或换计数结构。
追问「哪些数重复了」时，答案不是改代码，是改数据结构。
十、面试怎么答
30 秒版本：
10 亿个 int32 原样放是 4 GB，但值域有界 —— 开一张位图，每个可能取值 1 bit，值域 10^9 就是 119 MiB。逐个数置位，重复的再置那一位已经是 1，天然去重；最后按 bit 下标扫一遍，天然有序。时间 O(n + 值域)，空间 O(值域 / 8)，压缩比 32 : 1。
如果还有时间，主动补三句，分别是三个加分点：
- 位运算三件套：
word = v >> 5、bit = v & 31、置位 |=、清位 &= ~—— 波浪号和或号是两道送命题；
- 2-bit 位图：加一个 bit 就能同时回答「出现过 / 重复了 / 只一次」，空间翻倍换次数分档；
- 值域爆炸的退路：64 位场景先范围分桶再桶内位图，或者直接外排 —— 位图是「有界值域」的特例，不是万能药。
这套题的完整状态机、渲染层和 26 个单测（含与
set /
Counter 参考解各 3000 组随机对拍）都在仓库里，动画对应文章里的两个占位符。