bitwise operators with an if

Question

I am reading K&R book for c language and in section 2.10 they give the following example:

/*bitcount: count 1 bits in x*/
int bitcount(unsigned x)
{
    int b; 
    for(b=0; x!=0;x>>=1)
       if(x&01)
           b++;
     return b;

}

The function supposed to count the bits that are 1 in x.

I understand that the if is supposed to "mask off" the bits, but I don't understand how?

Is This condition is basicly:

if(x&01==1)?

I don't understand this condition.

What does (x&01) mean?

Also, I don't understand when does the loop stop? whenever all the bits have been shifted to right and all the vacated cells are now 0?

I just can't understand how this method works, and I looked for a solution quite a while.

Thank you.

Answer 1

You understood right about loop termination.

But however an important note: This code will work only if x is unsigned. Because for a signed integer 1 bit is appended as MSB on right shift.

Now (x & 01 == 1):

It basically ANDs the value of x to decimal number 1 like this:

x:           0001000100001110 (Some random 32 bit value)
1:           0000000000000001
&
Result:  0000000000000000

Reason for this result:
AND operation does a bit by bit logical AND. You can check the truth table for AND operation on internet.

A tip/hint for you: This is not the best method to count all the 1 bits in a signed/unsigned number. There exists a method which can count 1 bits in as many loop iterations as there are number of 1s in the number. Try yourself to implement it or search for that better method.

Answer 2

Let's rewrite the function using a while loop.

int bitcount(unsigned x)
{
    int b = 0;
    while (x != 0) {
        if (x & 0x1)
            b++;
        x = x >> 1;
    }

    return b;
}

Note that each iteration of the loop, we do two things:

1. If the bottom bit of the number is high (the number is odd), then we add one to our counter of bits.
2. Each iteration, we divide the number by 2 (x = x >> 1).

Answer 3

Is This condition is basicly: if(x&01==1)?

Kind of, the condition in other words: if the "x & 01" is non-zero.

Also, I don't understand when does the loop stop? whenever all the bits have been shifted to right and all the vacated cells are now 0?

When you do x>>=1, you are shifting all the bits x to the right by 1 step. If you take a pen and paper, you will also realize that this is same as dividing by 2. When will it stop? When this x becomes zero: x!=0.

Answer 4

if(x&01) means:

for example1: x's binary value is : 1011101
                      01's binary value is: 0000001
                      & is binaryopAND : ---------
                                       result is : 0000001

for example2: x's binary value is : 1011100 (last bit is 0)
                      01's binary value is: 0000001
                      & is binaryopAND : ---------
                                       result is : 0000000

so this means if(x&01) :
this condition returns only 2 values "0000001" or "0000000" according to x's last bit value "1" or "0".

int bitcount(unsigned x):
x is defined as unsigned
this means x can be only a positive value.
cuz ungsigned means only positive numbers.
0000000 is NOT POSITIVE NUMBER = NOT UNSINGED NUMBER.

so b++; :
since "x" is defined in only postive numbers, x won't accept 0000000 value cuz 0000000 is a not postive number. This will only count values are 0000001.

finally x >>= 1 :
this will shift x's bits 1 slot to the right-side and will fill the new slot bit that created at the most-left with "0" value.

and x != 0:
"for" loop will end when x comes to 0000000 in the end of process of right-side shifting eventually.