# ..MindWrite..

• 27,094
• ## Author over at this website on Interesting read about Interne… Gmail Inbox Tabs and… on Malkovich Bias guptaradhesh on Yahoo acquires Tumblr! Great…

# Posts Tagged ‘binary manipulations’

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