Author: Gour Ch. Saha
Contact for any query:: gour_ch_saha@yahoo.co.in
The normal conventional method to count the number of bits in interger
is given below:-
## Interger Bit Count version 1.0

int bit_count(int num)
{
int count=0;
while(num)
{
if(1&num)
{
count++;
}
num=num>>1;
}
return count;
}
The disadvantage of this method of bit count is
it will enter in infinite loop if the input number is negative.
For example if the input is -4
After 1st iteration: num = -2
After 2nd iteration: num = -1
After 3rd iteration: num = -1
.
.
.
After nth iteration: num = -1
and it will be infinite loop.
We can modify the bit count algorithm so that it can over come this situation.
So the modified version of conventional bit count of interger algo will be as follows
## Interger Bit Count version 2.0

int bit_count(int num)
{
int count=0;
while(num)
{
if(1 & **(unsigned int)**num)
{
count++;
}
num=**(unsigned int)**num>>1;
}
return count;
}
In this Interger bit count algorithm or c code We have to iterate non zero MSB's
position time means if the input is 64(in binary 1000000) then the position of non
zero MSB is at 7 th position. So the number of iteration will be 7.
Though there is only one "1" in the input number 64 yet in this interger bit count
algo we have to iterate 7 times.
Now we can overcome this also. So the most efficient algorithm or c code to
count the number of one in an interger is-
## Interger Bit Count version 3.0

int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}