Why does this function count the number of given bits in integers
In an interview, I was asked the following question:
int foofoo(unsigned int u) {
unsigned int foo = u;
do{
u = u/2;
foo -= u;
}while(u > 0);
return foo;
}
I was asked to tell you what this function does and I was able to find that it counts the number of bits of a set into an unsigned int value, but I could not prove it, maybe someone can?
source to share
I was able to find that it counts the number of given bits in an unsigned value, but I couldn't prove it, maybe someone can?
Look at the single bit m
inside U
. This bit contributes to the meaning U
, for example:
U = ...... + U m 2 ^ m + ..... (where .... represents other bits).
In each cycle, the bit is divided by 2 and then subtracted from U
. When the loop is complete, it looks like the line below for bits m
:
U m 2 ^ m - U m 2 ^ (m-1) - U m 2 ^ (m-2) -.... - U m 2 ^ 0
It can be rewritten like this:
U m (2 ^ m - (2 ^ (m-1) + 2 ^ (m-2) + .... + 2 ^ 0))
U m (2 ^ m - (2 ^ m -1))
U m (2 ^ m - 2 ^ m + 1)
U m
So from this you can see that the bit m
contributes to the final result with its bit value (i.e. 0 or 1). This is the reason it matters for all bits in the U
. Therefore:
foo
= U n-1 + U n-2 + ... + U m + ... + U 1 + U 0
Therefore, the result will be equal to the number of bits set to U
.
ps I tried using superscript to make the formulas look better. But I couldn't get the job done <sup>
. Feel free to edit formulas if you know how.
source to share
Idea
It is known that an unsigned integer u
can be represented as the sum of powers of two:
u = A * 2ª + ... + N * 2ⁿ,
where 0 <= a < ... < n
are integers, and A, ..., N
are either zeros or from them. If we remove the members of the zero product, the number of terms will be equal to the number of bits (ones) set. For example,1101
b= 2⁰ + 2² + 2³ consists of three terms (powers of two), and the number of set bits is also three.
The idea is to find the number of non-zero terms in this view.
Algorithm
If expressed u
as the sum of the powers of two:
u = 2ª + ... + 2ⁿ
where 0 <= a < ... < n
, then integer division u = u / 2
can be expressed as:
u = ( 2ª + ... + 2ⁿ ) / 2
or, equivalently:
u = ( 2ª / 2 ) + ... + ( 2ⁿ / 2 )
(Since, generally speaking,. (x + y) / 2 = (x / 2) + (y / 2)
)
The process is repeated and u
is positive. Thus, each term eventually becomes equal to one. In the next iteration, it becomes equal to zero due to the integer division rules: 1 / 2 = 0
.
The resulting value ( u
) is subtracted from the initial value stored in foo
: foo -= u
.
So we end up subtracting everything from the original value foo
except "divided by two" ( 1 / 2
) .
Obviously, the number of occurrences 1 / 2
is equal to the number of nonzero members in the original expression u
, which is equal to the number of bits set (as we found out above). Therefore, the remaining value "n" foo
is the sum of the remainders " 1 / 2
", that is, the number of terms, which is also the number of bits set.
Example
Provide a visualization of the process by example u = 13
.
The binary representation of a decimal number 13
is 1101
. So, the sum of the powers of two in decimal notation:
u = 2⁰ + 2² + 2³
First iteration:
u = u / 2 = (2⁰ + 2² + 2³) / 2 = (2⁰ / 2) + (2² / 2) + (2³ / 2) = 0 + 2 + 2²
Until now, we have one zero: 2⁰ / 2 = 1 / 2 = 0
.
Second iteration:
u = u / 2 = (2 + 2²) / 2 = (2 / 2) + (2² / 2) = 1 + 2
There are no more zeros in this iteration. Third iteration:
u = u / 2 = (1 + 2) / 2 = (1 / 2) + (2 / 2) = 0 + 1
We got second zero in this iteration 1 / 2 = 0
.
The fourth iteration gives the third zero:
u = u / 2 = 1 / 2 = 0.
The number of zeros is equal to the number of bits set, i.e. 3
...
source to share
I answer a little late.
I would answer by rewriting the program in an equivalent form ...
#include <stdio.h>
unsigned
count(unsigned u) {
unsigned foo=u, u0=0;
do
u0+=u>>=1;
while(u);
return foo-u0;
}
void
main()
{
printf("%u\n", count(7));
}
As an example, let's see what happens for U=10110
(1s spread diagonally when shifted to the right):
10110 1011 101 10 1
As you can see, for every 1 bit in position N representing a number 2^N
(so charging u with 2 ^ N), U0 will be charged with 2^0+2^1+ ... + 2^(N-1)
which is 2^N-1
.
So, for every bit set to 1, U0
will lose 1. By writing U as a binary sum, we will lose 1 for every bit set to 1.
source to share