Let us make a simulation for a user who entered the number \(\displaystyle 26 = 11010\).
\(\displaystyle \text{counter} = 0\)
\(\displaystyle \text{Step} \ \bold{1}\)
if \(\displaystyle 26 = 0\) or \(\displaystyle 26 = 1\),
stop \(\displaystyle \rightarrow\)
false, then
continue.
\(\displaystyle \text{Step} \ \bold{2}\)
if \(\displaystyle 26\) is
even,
divide by \(\displaystyle 2\) \(\displaystyle \rightarrow\)
true, \(\displaystyle \frac{26}{2} = 13\)
\(\displaystyle \text{Step} \ \bold{3}\)
if \(\displaystyle 13 = 0\) or \(\displaystyle 13 = 1\),
stop \(\displaystyle \rightarrow\)
false, then
continue.
\(\displaystyle \text{Step} \ \bold{4}\)
if \(\displaystyle 13\) is
odd,
divide by \(\displaystyle 2\) and
add one to the counter \(\displaystyle \rightarrow\)
true, \(\displaystyle \left\lfloor\frac{13}{2}\right\rfloor = 6\) \(\displaystyle (\text{counter} = 1)\)
\(\displaystyle \text{Step} \ \bold{5}\)
if \(\displaystyle 6 = 0\) or \(\displaystyle 6 = 1\),
stop \(\displaystyle \rightarrow\)
false, then
continue.
\(\displaystyle \text{Step} \ \bold{6}\)
if \(\displaystyle 6\) is
even,
divide by \(\displaystyle 2\) \(\displaystyle \rightarrow\)
true, \(\displaystyle \frac{6}{2} = 3\)
\(\displaystyle \text{Step} \ \bold{7}\)
if \(\displaystyle 3 = 0\) or \(\displaystyle 3 = 1\),
stop \(\displaystyle \rightarrow\)
false, then
continue.
\(\displaystyle \text{Step} \ \bold{8}\)
if \(\displaystyle 3\) is
odd,
divide by \(\displaystyle 2\) and
add one to the counter \(\displaystyle \rightarrow\)
true, \(\displaystyle \left\lfloor\frac{3}{2}\right\rfloor = 1\) \(\displaystyle (\text{counter} = 2)\)
\(\displaystyle \text{Step} \ \bold{9}\)
if \(\displaystyle 1 = 0\) or \(\displaystyle 1 = 1\),
stop \(\displaystyle \rightarrow\)
true, if the number is \(\displaystyle 1\),
add one to the counter \(\displaystyle (\text{counter} = 3)\)
And that's how we got the number of ones \(\displaystyle = 3\). In fact, that \(\displaystyle \text{counter}\) does not exist. The function just calls itself and keeps track of the ones when the number is odd. I put the \(\displaystyle \text{counter}\) just to give your brain an imaginary visualization of the process.
Some of you may be wondering, how all this magic happens. In simple words, I have used the concept of the
Hamming Weight.
