编程笔记

按位二分找缺失整数

3分钟阅读

A2 · 按位二分找缺失整数

来源：《编程珠玑》开篇问题 A（仅几百字节内存 + 临时文件）

题意

同 位图篇：在最多 40 亿个 32 位整数里找一个缺失值。
约束改为：

  • 内存只有几百字节
  • 可用若干临时文件

这不是「空间换时间」，而是 时间换空间（多趟扫描，省内存）。

思路

从高位到低位，每一位把当前文件拆成两堆：

  1. 当前位为 0 → 临时文件 A，并计数 count0
  2. 当前位为 1 → 临时文件 B，并计数 count1
  3. 该位为 0 / 1 的完整容量各是 (2^{\text{bit}})
  4. 哪边 count < capacity，缺失就在哪边；丢掉满的一边，对不满的一边看下一位
  5. 共约 32 轮，锁定一个完整缺失值

容易卡的点

第一轮选中「最高位=0」那堆后，堆内最高位确实都一样。
但第二轮看的是 bit30，不是再看 bit31——还没定的位仍然有 0/1，可以继续拆。

原理图

新标签打开流程图

交互演示

新标签打开演示

Java 伪代码

/** 区间版：每轮砍半答案区间 [lo, hi]，并保留对应临时文件 */
long findMissing(File input) {
    File current = input;
    long lo = 0L;
    long hi = (1L << 32) - 1L; // 0 .. 2^32-1
 
    for (int bit = 31; bit >= 0; bit--) {
        File zeros = tempFile();
        File ones = tempFile();
        long count0 = 0, count1 = 0;
 
        try (var in = open(current);
             var out0 = openWrite(zeros);
             var out1 = openWrite(ones)) {
            while (hasNextInt(in)) {
                int x = readInt(in);
                long ux = Integer.toUnsignedLong(x);
                if (((ux >>> bit) & 1L) == 0L) {
                    out0.writeInt(x);
                    count0++;
                } else {
                    out1.writeInt(x);
                    count1++;
                }
            }
        }
 
        long capacity = 1L << bit;
        long mid = (lo + hi) >>> 1;
 
        if (count0 < capacity) {
            hi = mid;                 // 缺在「该位=0」
            if (current != input) delete(current);
            delete(ones);
            current = zeros;
        } else {
            lo = mid + 1;             // 缺在「该位=1」
            if (current != input) delete(current);
            delete(zeros);
            current = ones;
        }
    }
    return lo; // lo == hi，即为缺失值之一
}

取当前位：

((x >>> bit) & 1)   // >>> 是无符号右移，不是左移

复杂度

时间约 (O(n \cdot 32) = O(n \log U))，多趟读文件
空间内存 (O(1))；外存靠临时文件

位图更低时间、更大内存 → A1 位图

系列