Quick Links
Categories
Links
How to count the number of 1's (set bits) in a given number ?
This is another question that confounds most of the newbies in Orkut and they end up confusing themselves and the others.
There are many ways you can do this, below are a few naive methods for the beginners:
int countBits(unsigned num){
int count= 0;
while(num){
count += num & 1;
num >>= 1;
}
return count;
}
int count= 0;
while(num){
count += num & 1;
num >>= 1;
}
return count;
}
int countBits(unsigned num){
for(unsigned int count=0; num; count++){
num&=num-1;
}
return count;
}
for(unsigned int count=0; num; count++){
num&=num-1;
}
return count;
}
Here is how you can do it in C++ using the bitset class provided in the STL.
int countBits(int num){
std::bitset<sizeof(int)*8> temp(num);
return temp.count();
}
std::bitset<sizeof(int)*8> temp(num);
return temp.count();
}
Please refer to this site Bit Twiddling Hacks∞ to learn many other methods to count bits, which are much more efficient than the above methods, and they manipulate bits at the lowest level.
Comments [Hide comments/form]
Hi,
In the first example I think we have to chnage the while condition as follows:
while(num=num>>1)
{
(num&1) ? ++count : count;
}
Other wise the program will enter into a infinte loop
In the first example I think we have to chnage the while condition as follows:
while(num=num>>1)
{
(num&1) ? ++count : count;
}
Other wise the program will enter into a infinte loop
-- byethost15.com (2006-11-09 01:27:31)
Thanks for pointing that out. I have changed it now.
-- PriyaSridharan
(2006-11-09 03:20:26)
Just being pedantic, but this would be more 'elegent' for the inelegent first solution :
int countBits(unsigned num){
int count= 0;
while(num){
count += num & 1;
num >>= 1;
}
return count;
}
int countBits(unsigned num){
int count= 0;
while(num){
count += num & 1;
num >>= 1;
}
return count;
}
-- byethost15.com (2006-11-28 23:04:11)
Yeah agree.
-- PriyaSridharan
(2006-12-11 20:28:15)
Page was generated in 0.0546 seconds