Number of $1$'s in a binary number

Question

I'm working on a function $\zeta(\xi)$ that takes as input an integer $\xi$ (in base $10$) and calculates how many $1$'s there are in its binary representation. How can I write such function?

Here is a graph of $\zeta(\xi)$, for $0\leq\xi\leq250$, created in Excel:

By now, I have tried only brute-forcing: calculate a lot of values of $\zeta(\xi)$ to try to find a common pattern, but this doesn't seem helpful in finding an explicit formula. Any idea?

Answer 1

Here you go: $$ f(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ n \bmod 2 + f(\lfloor \frac{n}{2} \rfloor) & \text{else} \end{cases} $$

This exactly matches @ViktorGlombik's observation in the comments (no surprise!) If you prefer, there's $$ f(n) = \sum_{i = 0}^n \left( \lfloor\frac{n}{2^i}\rfloor \right) \bmod 2. $$

And if you don't like the use of $k \bmod 2$, you can replace it by $k - 2\lfloor\frac{k}{2}\rfloor$ (which works for nonnegative $k$ at least, which appears to be what you care about).

And if you don't like the use of "floor", you can replace it by $$ \lfloor x \rfloor = x - \frac12 + \frac{1}{\pi} \sum_{k=1}^\infty \frac{\sin (2 \pi k x)}{k}. $$

But honestly --- all that work to express as a double-sum a thing for which you've already got a working program? It's hard to see the value here. If you want to do it, go for it.

Answer 2

For computer applications, there is hardware support for this problem:

Intel CPU Nvidia GPU

Here is an algorithm in C from Brian Kernighan:

uint64_t countBits(uint64_t input){
uint64_t counter;
for(counter=0; input > 0; counter++)
    input &= (input - 1); /*clear the set lsb*/
return counter;
}

Answer 3

I'm pretty sure you want your function to take input as a binary number -- otherwise most of the work would lie in converting from a decimal representation to the machine's native binary.

In the absence of special hardware support for this operation (often known as popcout for binary "population count"), the usual trick is to squeeze a tree of parallel additions into a single word, by periodically masking out spurious bits that would produce carries between the sub-additions:

uint64 popcount(uint64 x) {
   x = (x & 0x5555555555555555L) + ((x >> 1) & 0x5555555555555555L);
   x = (x & 0x3333333333333333L) + ((x >> 2) & 0x3333333333333333L);
   x = x + (x >> 4);
   x = x & 0x0F0F0F0F0F0F0F0FL;
   x = x + (x >> 8);
   x = x + (x >> 16);
   x = x + (x >> 32);
   return x & 0xFF;
}

Answer 4

Specifically for binary base, the number of 1's is equel with the sum of the digits in base 2. E.g. $$\zeta(5_{10})=\zeta(101_{2})=1+0+1=s_2(5_{10})=2$$ And then, there is this formula and one that can be derived from this result. $$s_2(n)=n-\nu_2(n!)=n-\sum\limits_{k=1}\left \lfloor \frac{n}{2^k} \right \rfloor$$

By the way, zeta ($\zeta$) is too famous to be redefined.