考虑区间[2 i .. 2 i + 1-1]中的所有整数。并假设所有低于2 i的整数都可以由给定数组的数字之和形成。还要假设我们已经知道C，它是2
i以下所有数字的总和。如果C> = 2 i + 1-1，则此间隔中的每个数字都可以表示为给定数字的总和。否则，我们可以检查区间[2 i .. C
+1]是否包含给定数组中的任何数字。如果没有这样的数字，我们将搜索C + 1。

这是算法的草图：

1. 对于每个输入数字，确定它属于哪个间隔，并更新相应的总和：S[int_log(x)] += x。
2. 计算数组S：的前缀和foreach i: C[i] = C[i-1] + S[i]。
3. 过滤数组C以仅保留值小于下一个2的幂的条目。
4. 再次扫描输入数组，请注意哪个间隔[2 i .. C +1]至少包含一个输入数字：i = int_log(x) - 1; B[i] |= (x <= C[i] + 1)。
5. 查找在步骤＃3中未滤除的第一间隔和B[]在步骤＃4 中未设置的对应元素。

如果不清楚为什么我们可以应用步骤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是机器字中的位数。