..MindWrite..

Posts Tagged ‘number of 1’s’

algorithm to determine number of 1’s in binary representation of a number

Posted by guptaradhesh on November 3, 2010

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;
}

Posted in puzzles/ algorithms | Tagged: , , | 1 Comment »