Is there an equation for the amount of ones in a binary number?

Question

We know that any natural number can be expressed as a binary number. Is there an equation or algorithm for the amount of ones in a binary number? I tried searching for this, but all I could find were computer codes to calculate it. I'm looking for an actual mathematical function. Is there one? If so, what is it? I believe this is also called the Hamming weight. Any help would be appreciated, even links or references. Thank you.

Answer 1

Sum of the binary digits of a natural number $n$ is $$n-\sum_{i=1}^\infty \lfloor n/2^i\rfloor.$$

Note that this sum has at most $\log_2(n)$ nonzero summands.

I thought this formula should be all over the Web but could not find it. Here is the proof. Let $r(n)$ denotes the last binary digit of $n$. Then $r(n)=n-2\lfloor n/2\rfloor$. The sum of binary digits of $n$ is $$r(n)+r(\lfloor n/2\rfloor)+r(\lfloor n/4\rfloor)+... $$ which implies the formula.

Answer 2

For sequences like this, I suggest you try The On-Line Encyclopedia of Integer Sequences. You're likely to find something related to what you want.

Answer 3

Recursively...

Let $a_n$ be the number of $1$s in the binary representation of $n$. Then $a_0=0$, $a_1=1$, and $a_n=1+a_{n-2^{\lfloor\log_2(n)\rfloor}}$.

For example, $$ \begin{align} a_{23}&=1+a_{7}&a_{24}&=1+a_{8}\\ &=1+1+a_{3}&&=1+1+a_{0}\\ &=1+1+1+a_{1}&&=1+1+0\\ &=1+1+1+1 \end{align} $$ This approach has speed roughly $c\cdot a_n$, where $c$ is how long it takes to compute $n-2^{\lfloor\log_2(n)\rfloor}$. An approach that sums after dividing by powers of $2$ has speed roughly $d\log_2(n)$, where $d$ is the time to compute a division by a power of $2$. I think in general the recursive approach is faster, but I am not offering a proof.