What is the total running time of counting from 1 to n in binary if the time needed to add 1 to the current number i is proportional to the number of bits in the binary expansion of i that must change in going from i to i + 1?
Having trouble getting my head a around this one because I cannot find a formula for how bits change from some i to i+1. for example
$$~~~~before~~~~~~after~~~~changes$$
$$0000 -> 0001 = 1$$
$$0001 -> 0010 = 2$$
$$0010 -> 0011 = 1$$
$$0011 -> 0100 = 3$$
Best Answer
The number of bit changes required to increment up to a number is equal to the number of trailing zeros after the last one. Say we are incrementing through an $n$-bit register which represents $2^n$ different numbers. Then we can count the total amount of numbers with $k$ trailing zeros after the final one.
For $k=0,$ this is easy: it is just the odd numbers so there are $2^{n-1}$ that require one bit flip. For $k=1,$ the last two bits are fixed to $1$ and $0$, while the others are free to be whatever, so there are $2^{n-2}$ possibilities. That's the pattern. For general $k$ there are $2^{n-k-1}$ different numbers that have $k$ trailing zeros after the last one. Since there are $k+1$ bit flips for a number with $k$ trailing zeros we have $$ N = \sum_{k=0}^{n-1}(k+1)2^{n-k-1} = 2^{n+1}-n-2$$
for counting from $0$ to $2^n-1.$