Going by the brute force approach, it would be easy to come up with the following solution. If the least significant bit of a number is 1, it will return a result of 1 when we AND it with 1. Using this logic, we can shift bits in the number to the right and keep testing if the least significant bit is 1. When there are no 1′s left in the number, it will become zero. Here’s some code to illustrate this simple logic.
int numOnesInInteger( int num )
{
int numOnes = 0;
while( num != 0 )
{
if( ( num & 1 ) == 1 ) {
numOnes++;
}
num = num >> 1;
}
return numOnes;
}
Think we can do better? The above algorithm runs in O(n) where n in the number of bits in the integer. Maybe we can make this a tad better. But this would need some real creative bit manipulation skills. So let’s think, what happens to a number when it we AND it with (number – 1). Let’s take 7 (0111) as an example.
7 & 6 = 0111 & 0110 = 0110 = 6
6 & 5 = 0110 & 0101 = 0100 = 4
4 & 3 = 0100 & 0011 = 0000 = 0
Do you see a pattern yet? Essentially, when you AND a number with (number – 1), the last 1 bit in the number gets set to zero. So if we continue to set every 1 bit in the number to zero, the number will eventually become zero. If we use this logic to count the number of 1s, we have an algorithm that runs in O(m) where m is the number of bits set to 1 in the number. Here’s some code.
int numOnesInInteger( int num )
{
int numOnes = 0;
while( num != 0 ){
num = num & (num – 1);
numOnes++;
}
return numOnes;
}
Interesting right? Please Digg or Stumble this post! As usual, comments are always welcome.
Live to Seek... 