algorithm - 计数到 N 的位模型成本

Question

考虑一个类似于教科书加法的计算模型，其中每个操作花费 1 个单位，二进制加法计数到 n 的位模型成本是多少，其中 n 是二的幂？

模型

计算模型基于上面写有 0 和 1 的玩具积木。最初，零 block 位于 table 上(免费)。每个 block 操作(删除或添加 block )花费 1 个单位。

目标是用 1, 2, 3, ..., n 代替表上的(二进制)数。这是通过模仿 add-with-carry 完成的。

例如，我们从 0 开始。要计数到 1，我们需要删除 0(成本 1)并添加 1(成本 1)。然后，要数到 2，我们需要加 1(成本 1)。然后我们删除两个(成本 2)，替换为 0(成本 1)并在前面添加 1(成本 1)以制作 10(基数 2)(成本 1)。以此类推，直到 n。

我算了一下，当最低有效位为0时，cost为2(去掉0，加1)。当 lsb 为 1 时，cost 为 5。

递增数字的成本

0000 ->  0           (0 time unit to go to 0 - block already there)
0001 ->  2           (2 operations to go to 2)
0010 ->  1*4 + 1     (1 carry)
0011 ->  2
0100 ->  2*4 + 1     (2 carries)
0101 ->  2
0110 ->  5
0111 ->  2
1000 ->  3*4 + 1     (3 carries)
1001 ->  2
1010 ->  5
1011 ->  2
1100 ->  2*4 + 1
1101 ->  2
1110 ->  5
1111 ->  2
10000 ->  4*4 + 1
10001 ->  2
10010 ->  5
...

我开始看到一种模式，但无法将其形式化。

它看起来像 T(n) = 从 k = 1 到 log n (4k +1) + 9 * 2^(log n - 2) 的总和。

Answer 1

思考这个问题的一种方法是对列而不是行求和。假设您数到 2^k。然后:

• 在所有 2^k 操作中，1 的位将翻转。
• 在 2^k/2 = 2^k-1 次操作中，2 的位将翻转。
• 在这些操作的 2^k/4 = 2^k-2 中，4 的位将翻转。
• 在 2^k/8 = 2^k-3 次操作中，8 位将翻转。
• ...
• 在 2^k/2^k = 1 次操作中，2^k 的位将翻转。

(在上面，我将添加一个新的 1 数字算作“翻转”而不是“添加”，因为您可以将其视为从 0 翻转到 1 或将新的 1 数字添加到前面。)

这意味着必须更改的总位数由下式给出

2^k + 2^k-1 + 2^k-2 + ... + 1

= 2^k+1 - 1

因此总共将翻转 2^k+1 - 1 位。我们可以检查一下:从 0 数到 1，我们得到

0
1

所以翻转了一位(1 = 2¹ - 1，正如我们预测的那样)。当从 0 数到 2 时，我们得到

00
01
10

总共有三个位翻转(0 -> 1 -> 0 在 1 的位置，0 -> 1 在 2 的位置)，并且 3 = 2² - 1，因为我们猜对了。

希望这对您有所帮助!