Having trouble understanding a portion of code (bit operation)

Question

I can't understand how to count number of 1's in binary representation.

I have my code, and I hope someone can explain it for me.

Code:

int count (int x)
{
    int nr=0;
    while(x != 0)
    {
        nr+=x%2;
        x/=2;
    }
    return nr;
}

1. Why while ? For example if i have 1011, it wouldn't stop at 0?

2. Why nr += x%2 ?

3. Why x/=2 ?!

Answer 1

First:

nr += x % 2;

Imagine x in binary:

...1001101

The Modulo operator returns the remainder from a / b.

Now the last bit of x is either a 0, in which case 2 will always go into x with 0 remainder, or a 1, in which case it returns a 1.

As you can see x % 2 will return (if the last bit is a one) a one, thus incrementing nr by one, or not, in which case nr is unchanged.

x /= 2;

This divides x by two, and because it is a integer, drops the remainder. What this means is is the binary was

....10

It will find out how many times 2 would go into it, in this case 1. It effectively drops the last digit of the binary number because in base 2 (binary) the number of times 2 goes into a number is just the same as 'shifting' everything down a space (This is a poor explanation, please ask if you need elaboration). This effectively 'iterates' through the binary number, allowing the line about to check the next bit.

This will iterate until the binary is just 1 and then half that, drop the remainder and x will equal 0,

while (x != 0)

in which case exit the loop, you have checked every bit.

Also:

'count`is possibly not the most descriptive name for a function, consider naming it something more descriptive of its purpose.

nr will always be a integer greater or equal to zero, so you should probably have the return type unsigned int

Answer 2

int count (int x)
{
    int nr=0;
    while(x != 0)
    {
        nr+=x%2;
        x/=2;
    }
    return nr;
}

This program basically gives the numbers of set bits in a given integer.

For instance, lets start with the example integer 11 ( binary representation - 1011). First flow will enter the while loop and check for the number, if it is equal to zero. while(11 != 0)

Since 11 is not equal to zero it enter the while loop and nr is assigned the value 1 (11%2 = 1).nr += 11%2; Then it executes the second line inside the loop (x = x/2). This line of code assigns the value 5 (11/2 = 5 ) to x.

Once done with the body of the while loop, it then again checks if x ie 5 is equal to zero. while( 5 != 0). Since it is not the case,the flow goes inside the while loop for the second time and nr is assigned the value 2 ( 1+ 5%2). After that the value of x is divided by 2 (x/2, 5/2 = 2 )and it assigns 2 to x. Similarly in the next loop, while (2 != 0 ), nr adds (2 + 2%2), since 2%2 is 0, value of nr remains 2 and value of x is decreased to 1 (2/2) in the next line. 1 is not eqaul to 0 so it enters the while loop for the third time.

In the third execution of the while loop nr value is increased to 3 (2 + 1%2). After that value of x is reduced to 0 ( x = 1/2 which is 0).

Since it fails the check (while x != 0), the flow comes out of the loop.

At the end the value of nr (Which is the number of bits set in a given integer) is returned to the calling function.

Best way to understand the flow of a program is executing the program through a debugger. I strongly suggest you to execute the program once through a debugger.It will help you to understand the flow completely.