Bit Operation #1

Bit operation is very often asked in job interviews and can be very tricky. Here, I am going to brush up bit operation problems that can be expected in my future job interviews.

Input: 4 bits integer x (e.g., 1010)

int f(unsigned int x)
{
    int a = 0;
    while (x != 0)
    {
        x = x & (x-1);
        ++a;
    }
    return a;
}

Let's think of what (x-1) is in the case of x = 1010. (x-1) is 1001 because the rightmost bit of 1 in x is changed to 0 and all 0 bits to the right are changed to 1. Look at this details.
1 0 1 0
      |  |
      v  v
1 0 0 1

We can easily get the result after applying & operation for x and (x-1).
    1 0 1 0
& 1 0 0 1
-----------
    1 0 0 0

Hence, the result of & operation in while statement shows that the rightmost 1 bit of x turns to 0. Finally, if we do this operation until x become zero (0000), the variable 'a' will count the number of 1 bit in x.