Finding the Number of $1$ in a Binary String

Question

Is there a general formula/ recurrence relation for finding the number $N$ of $1$ in an $n$ binary string representation of an integer $I$ ?

For the simplest case where $I\mod{2^n}=0$, it is easily seen that $N=1$

For $I=2^n+c\ \ \ \ $ where $\ \ \ \ c=2^{n-1}$, we have $N=2$

---

Now, when $2^n>c≥2^{n-1}$, we have $N=2+d$

if $c-2^{n-1}>2^{n-2}$, we have $d=1+e$ so $N=3+e$ and so on,

The process is so limited that it requires $I≥2^n$ so a modification is done to change $n$. Is this process correct? Or is there any series/ generalization for the formula in counting the number of $1$ in a binary string of an integer?

Answer 1

Brian Kernighan's method is a well known algorithm for counting the set bits in a word. Here is some pseudocode:

count = 0;
while (I != 0) {
  I &= (I - 1);
  count++;
}
return count;