Weighted binary counter cost ($C(n,k)={\sum }_{i=0}^{k-1}{2}^i\lfloor n/2^i\rfloor$)

For an initially zero $k$-bit binary counter, suppose changing bit $i$ costs $2^i$. It changes exactly $\lfloor n/2^i\rfloor$ times in $n$ increments. Consequently the total is $\Theta (n\min \{k,1+{\log }_{2}n\})$ for $n,k\ge 1$. The upper bound counts at most $n$ cost at each active position; the lower bound uses $\lfloor x\rfloor \ge x/2$ for $x\ge 1$. This shows why exponential position costs cancel the decreasing carry frequencies that make the ordinary binary counter have constant amortized cost.