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.

## No comments:

Post a Comment