To determine the number of set bits in the binary representation of a number, the basic method would be-

Find if the least significant digit of the number is 1 or not by performing AND operation with 1. Keep shifting the bits and when there are no 1’s left, the number becomes zero.

This algorithm takes O(n) time.

I read an algorithm which performs real better. I actually likes the solution where in we can deduce the number of 1’s in O(m) time where m is the number of 1’s present in the number.

The basic login is to recognize a pattern where, ‘when we perform n AND (n-1) : last 1 bit of the number sets to zero’. So, the number of times we can do this will give the number of 1’s present in the number.

A short also snippet would be-

int numberOfOnes ( int num ){

int numOfOnes = 0;

while( num != 0 ){

num = num & (num – 1);

numOnes++;

}

return numOfOnes;

}