这是一个已解决的问题，我们必须从包含 40 亿个未排序无符号整数的文件形式的输入数据中找到缺失的整数。问题是只能使用 10 MB 的内存。
作者给出了一个解决方案，我们做 2 遍。在第一遍中，我们创建了一个一定大小的“块”数组。例如。块 0 代表0 to 999， 1 代表1000 to 1999，依此类推。因此，我们知道每个块中应该存在多少值。
现在我们扫描文件并计算每个块中实际存在多少值——这将导致我们找到丢失的整数。
我理解这种方法。但是，要计算适当的块大小，请从以下开始：
第一遍中的数组可以容纳 10 MB 或大约 2^23 字节的内存。
10MB 与有何相同之处2^23？我无法理解这个2^23数字是从哪里来的。
16MBytes2^24也是如此，所以他可能正在使用 10MBytes2^23或更少的最接近的值。如果是这样，他为什么不能使用整个 10 MBytes？即为什么他必须使用 2 的幂来获得这里的大小？
没有说明，但我假设问题是从具有一组 2^32 (4294967296) 个唯一的 32 位无符号整数的文件中找到一个缺失的整数，其值为 0 到 4294967295。该文件占用 17179869184 字节的空间。
使用 2^23 = 8388608 的内存空间允许将 2^21 = 2097152 32 位无符号整数计数保存在内存中。每组代表 (2^32)/(2^21) = 2^11 = 2048 个值。所以 count[0] 用于值 0 到 2047，count[1] 用于值 2048 到 4095，...，count[2097151] 用于值 4294965248 到 4294967295。循环内部的主线将是count[value>>21] += 1。除了与缺失整数对应的计数为 2047 外，所有计数均为 2048。第二遍只需读取适当范围内的 2047 个值即可找到缺失的整数。
另一种方法是使用 4194304 16 位计数，每组代表 1024 个值（最大计数值为 1024），但时间没有显着差异。
假设 10MB = 10 * 2^20 = 10485760，则可以使用 10 * 2^18 = 2621440 32 位计数，每个计数用于 1639 个值的范围（较小组的最后计数），这很尴尬。如果使用 16 位计数，则范围为 3278 个值，也很尴尬。
我相信它应该是 10*2^23 或 5*2^24 位。试试看是字节还是位
10 MB = 2*5*2^20*2^3
M=2^20
B=2^3b
10=2*5
它不是。
1 MB 是 2^20 字节 (1024 X 1024) = 1048576 10 MB 是 10485760。
2^23 = 8388608
当然，该网站说 10 MB 是“大约 2^23”，这可能是准确的，具体取决于粗略的含义。