Efficiently count the number of bits set in an integer

© Parineeth M R

Question 29. Efficiently count the number of bits set in an integer


One way to find the number of bits set in an integer is to check each bit. However there is a faster method to count the number of bits set using the function below

C/C++


unsigned int count_num_bits_set(unsigned int n)
{
	unsigned int count = 0;
	
	while (n) {
		n &= n - 1;
		count++;
	}

	return count;
}



Java


public static int countNumBitsSet(int n) {
	int count = 0;

	while (n != 0) {
		n &= n - 1;
		count++;
	}

	return count;
}



Python


#Returns the number of bits set to 1 in n
def count_num_bits_set(n) :
	count = 0

	while (n != 0) :
		n &= n - 1
		count += 1
	
	return count



The following code works because each time we perform the operation n &= n – 1, the first bit that has a value of 1 from the right (from the least significant bit) is reset to 0.

For instance if n = 1100, then

So 1100 is converted to 1000 where in the first bit that has a value of 1 from the right in 1100 is now reset to 0.