Bit Model Cost For Counting to N

Question

Considering a computational model resembling that of schoolbook addition where each operation cost 1 unit, what is the bit model cost for binary addition for counting to n where n is a power of two?

MODEL

The computational model is based on toy blocks that have 0 and 1 written on them. Initially, a zero block sits on a table (free). Each block operation (removing or adding a block ) costs 1 unit.

The objective is to replace the (binary) number on the table by 1, 2, 3, ..., n. This is done by imitating add-with-carry.

For example, we start with a 0. To count to 1, we need to remove the 0 (costs 1) and add a 1 (costs 1). Then, to count to 2, we need to add a 1 (costs 1). We then remove the two ones (costs 2), replace by a 0 (costs 1) and add a 1 (costs 1) in front to make 10 (base 2) (costs 1). And so on, until n.

I figured that when the least significant bit is 0, the cost is 2 (remove 0, add 1). When the lsb is 1, the cost is 5.

Costs to increment a number

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
...

I start to see a pattern, but can't formalize it.

It looks like T(n) = sum from k = 1 to log n of (4k +1) + 9 * 2^(log n - 2).

Answer 1

One way to think about this is to sum across the columns rather than the rows. Suppose you're counting up to 2^k. Then:

• In all 2^k operations, the 1's bit will flip.
• In 2^k / 2 = 2^k-1 of those operations, the 2's bit will flip.
• In 2^k / 4 = 2^k-2 of those operations, the 4's bit will flip.
• In 2^k / 8 = 2^k-3 of those operations, the 8's bit will flip.
• ...
• In 2^k / 2^k = 1 of those operations, the 2^k's bit will flip.

(In the above, I'm counting adding a new 1 digit in as a "flip" rather than an "add" because you can think of it as either flipping from 0 to 1 or adding a new 1 digit to the front.)

This means that the total number of bits that have to change is given by

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

= 2^k+1 - 1

So there will be a total of 2^k+1 - 1 bits flipped. We can check this: counting from 0 to 1, we get

0
1

So one bit is flipped (1 = 2¹ - 1, as we predicted). When counting from 0 to 2, we get

00
01
10

That's a total of three bit flips (0 -> 1 -> 0 in the 1's place and 0 -> 1 in the 2's place), and 3 = 2² - 1, as we guessed.

Hope this helps!