2010년 11월 9일 화요일

the number of ones in the number

There is a highly efficient scheme for counting the number of '1' bits in a 2's complement number that goes like the following:

CPP / C++ / C Code:
/*
* The statement inside the loop clears the
* least significant bit of the number.
*
* The loop terminates when all bits are zero.
*
* Therefore, the number of ones in the number
* is simply equal to the number of times the
* program goes through the loop.
*/


unsigned number_of_ones(unsigned x)
{
unsigned count;
for (count = 0; x != 0; count++) {
x &= x - 1;
}
return count;
}