1
$\begingroup$

I just read this result:

The number of bits in a positive $m$-bit integer $n$ is $n-\sum_{k=1}^{m-1} \lfloor n/2^k \rfloor$.

The proof is just outlined, and I thought that it would be interesting to see what proofs could be found.

The source also states that the sum of the digits of a positive $m$-digit integer $n$ is $n-9\sum_{k=1}^{m-1} \lfloor n/10^k \rfloor$.

$\endgroup$
1
$\begingroup$

You can also write this as $$ n - \sum_{k=1}^{\infty} \lfloor n/2^{k} \rfloor $$ because the terms for $k\ge m$ will be zero.

Now, we know that $$ \sum_{k=1}^{\infty} n/2^k = n $$

How much of this do we lose by the floor operation?

Well, each set bit in $n$ will appear once in $\sum_{k=1}^\infty n/2^k $ at each position to the right of the binary point. Therefore, for each set bit, the sum of exact fractions will exceed the sum of floors by $0.111\ldots_2 = 1$.

Thus, when we subtract the sum of floors from $n$, we get the number of bits that have contributed to a deficit in the sum-of-floors.


Alternatively, we can see by induction that $$ n - \sum_{k=1}^m \lfloor n/2^k\rfloor = \lfloor n/2^m \rfloor + \text{number of ones in the $m$ lowest bits of $n$} $$

Whenever we subtract half of the $\lfloor n/2^m\rfloor$ that's left, the remainder will be another half of it, plus one if the bit we just shifted out past the binary point was a one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.