© 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.