考虑区间[2 i .. 2 i + 1-1]中的所有整数。并假设所有低于2 i的整数都可以由给定数组的数字之和形成。还要假设我们已经知道C，它是2 i以下所有数字的总和。如果C> = 2 i + 1-1，则此间隔中的每个数字都可以表示为给定数字的总和。否则，我们可以检查区间[2 i .. C +1]是否包含给定数组中的任何数字。如果没有这样的数字，我们将搜索C + 1。
这是算法的草图：
如果不清楚为什么我们可以应用步骤3，那么这里就是证明。选择2 i和C 之间的任何数字，然后按从大到小的顺序依次减去2 i以下的所有数字。最终，我们得到的数字小于最后减去的数字或为零。如果结果为零，只需将所有相减的数字相加即可得到所选数字的表示形式。如果结果为非零且小于最后减去的数字，则此结果也小于2 i，因此它是“可表示的”，并且减去的数字均不用于表示。当我们将这些相减的数字相加后，便具有所选数字的表示形式。这也表明，与其一一过滤掉间隔，不如直接跳转到C的int_log来一次跳过几个间隔。
时间复杂度由function决定int_log()，它是整数的对数或数字中最高设置位的索引。如果我们的指令集包含整数对数或其任何等价形式（计数前导零或带浮点数的技巧），则复杂度为O（n）。否则，我们可以使用一些黑客手段int_log()在O（log log U）中实现并获得O（n * log log U）时间复杂度。（此处U是数组中最大的数字）。
如果步骤1（除了更新总和）还将更新给定范围内的最小值，则不再需要步骤4。我们可以将C [i]与Min [i + 1]进行比较。这意味着我们只需要单遍输入数组。或者我们可以将此算法应用于数组而不是数组。
几个例子：
Input: [ 4 13 2 3 1] [ 1 2 3 9] [ 1 1 2 9]
int_log: 2 3 1 1 0 0 1 1 3 0 0 1 3
int_log: 0 1 2 3 0 1 2 3 0 1 2 3
S: 1 5 4 13 1 5 0 9 2 2 0 9
C: 1 6 10 23 1 6 6 15 2 4 4 13
filtered(C): n n n n n n n n n n n n
number in
[2^i..C+1]: 2 4 - 2 - - 2 - -
C+1: 11 7 5
对于多精度输入数字，此方法需要O（n * log M）时间和O（log M）空间。其中M是数组中的最大数字。读取所有数字都需要花费相同的时间（在最坏的情况下，我们需要它们的每一位）。
仍然可以将此结果改进为O（n * log R），其中R是此算法找到的值（实际上是该算法的输出敏感型变量）。此优化所需的唯一修改不是立即处理整数，而是逐位处理它们：第一遍处理每个数字的低位（例如位0..63），第二遍处理- 下一位（例如64..127）等。找到结果后，我们可以忽略所有高阶位。同样，这将空间需求减少到O（K）个数，其中K是机器字中的位数。
602392714
清零编程群