我正在阅读有关在 Programming Pearls 中从一系列40亿32位整数中找到缺失数字的问题，但无法得到解决方案 .
给定一个顺序文件，其中包含最多4亿个随机顺序的32位整数，找到一个不在文件上的32位整数 . 约束：主内存的几个字节数，但在磁盘上充分使用extrernal暂存文件
所描述的解决方案是一个过程，我们使用高位分隔范围中的数字（在第一遍中我们将那些带有前导 0 位的数字写入一个文件，将带有 1 位的那些写入另一个文件 . 我们继续使用第二位使用新的搜索范围将半数除以一半，其中包含少于该范围内一半数字的一半 .
我用Google搜索并在SO中发现了一个类似的帖子，这个帖子并没有完全回答我的问题 how the exact number is found （我不知道二进制搜索如何适应不同的范围） .
@Damien_The_Unbeliever的答案似乎是最相关的，但从我的观点来看，我认为在这个过程之后我们最终得到2个文件：一个文件，其中2个数字在范围内，一个文件有1个数字 .
通过用一个文件中最大的一个减去一个文件中的（一个）数字，我们可以得到一个丢失的数字（不需要位掩码，我不太确定我们是否可以实际应用一个位掩码，因为该范围在任何时候都是未知的） .
我错了吗？有人可以帮忙解决这个问题吗？
3 回答
您无需复制数据本身或将任何内容写入磁盘;只计算一些数据分区的成员来识别开口 . 权衡是在通过次数和内存之间（更多内存允许更多计数，更小的分区） .
这是8次通过的解决方案 . 我们一次使用4位对数据进行分区 . 2 ^ 4 = 16个可能的值，因此我们需要64个字节来存储16个分区中每个分区的计数 . 因此每个4位半字节值都有一个相关的计数 .
传递数据，递增与数字前四位中的半字节匹配的相关计数 . 如果分区已满，则其计数将为2 ^ 28 . 选择一个未满的半字节 - 这将是你的结果的第一个半字节 .
将您的计数归零并再次传递，忽略与第一个半字节不匹配的数字，并递增与数字中第二个半字节相关的计数 . 完整的第二个半字节将具有2 ^ 24的值 . 选一个不满的 .
以这种方式继续，直到你有所有8个半字节，并且你的答案是O（N） .
如果你一次只检查一位，这将是一个需要32遍的二进制搜索 . （编辑：不是真正的二进制搜索，因为你仍然必须读取你为什么它被限制为几百个字节的值 - 可能是6比特/ 6个通道/ 256个字节？
编辑：Li-aung Yip的解决方案可以更好地扩展，并且很明显可以通过一个以上的位来修改它 . 如果写入比读取慢，那么最好的解决方案可能是这个只读答案和Li-aung Yip基于磁盘的解决方案之间的混合 .
如上所述进行计数半字节的通过，然后在计算第二组半字节时，根据第二个半字节，仅将与第一个半字节匹配的数字（或可能只是它们的最后28位）写入16个文件 .
选择你的第二个半字节并读取它以获得第三个半字节的计数，仅写入与第二个半字节匹配的数字，等等 . 如果文件接近容量，如果数字是相当均匀分布的，或者你选择的是最少的每次都要小字，你不得不写不超过文件大小的6.66％（1/16 1/16 ^ 2 ...） .
在将数字重复二进制分区为越来越小的文件后，您最终会得到：
一堆包含两个数字的文件，它们的最后一个有效位只有不同
一个文件中只有一个数字 .
通过翻转文件中最后一位数字来获取缺失的数字 .
以0x00到0x07的数字为例，缺少0x04：
拿
101，翻转最低有效位，得到100，这是缺失的0x04.使用32位整数表示4亿个整数 . 对自身进行异或运算是将汇编代码中的寄存器归零的标准技巧 . 如果保证只有一个数字丢失，整数上的按位异或就会出现救援，一种O（N）解决方案，只需要一个额外的32位整数空间 . 考虑一个简单的例子，一个3位数，因此数字0-7可以表示，其中一个缺失 . 假设6（110）缺失缺失= n1 XOR n2 XOR n3 XOR .. XOR n7 . = 000 XOR 001 XOR 010 XOR 011 XOR 100 XOR 101 XOR 111
如果问题是找到1到100之间缺少的数字，则需要从我的xoring开始必须排除的元素 . 通过屏蔽数字中的位，可以使用AND从32位整数范围下降到较小范围 .