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

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

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.