求一个整数的bit位中1的个数

ciedecem

给一个整数，求这个整数的bit位的1的个数，要求，最快算法:

int count(int ipNumber)
{
        int counter =0;
        int tmp(ipNumber);
        while( tmp != 0)
        {
                if ( tmp % 2 == 0)
                        tmp /=2;
                else
                {
                        ++counter;
                        tmp /=2;
                }
        }
        return counter;
}

我只想到了用将10进制转为2进制的方式，来求这个int数据中的bit位中1的个数。

可否使用移位运算，又该如何用？？还有没有其他方式？？

谢谢

塑料袋

这个有标准的算法的

32位的int，做4次移位和加法运算，就能算出来。

cdtits

这样行不？

1. int count(unsigned int num)
   
2. {
   
3.     int n = 0;
   
4.     while (num) {
   
5.         if (num & 1)
   
6.             n++;
   
7.         num >>= 1;
   
8.     }
   
9.     return n;
   
10. }

复制代码

塑料袋

unsigned int hweight32(unsigned int w)
{
        unsigned int res = w - ((w >> 1) & 0x55555555);
        res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
        res = (res + (res >> 4)) & 0x0F0F0F0F;
        res = res + (res >> ;
        return (res + (res >> 16)) & 0x000000FF;
}

塑料袋

1. 
   
2. unsigned int hweight32(unsigned int w)
   
3. {
   
4.         unsigned int res = w - ((w >> 1) & 0x55555555);
   
5.         res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
   
6.         res = (res + (res >> 4)) & 0x0F0F0F0F;
   
7.         res = res + (res >> 8);
   
8.         return (res + (res >> 16)) & 0x000000FF;
   
9. }
   

复制代码

以前哥们有一次去novell面试，上来就问脑筋急转弯。
第一个疯狗咬人，人不能咬疯狗的，不会。
第二个就是这个，我该装装B，可是当时想也没想，直接说这种题早就有标准算法了。
然后over


@pmerofc，专家，评论下这段代码呗？

noword2k

http://graphics.stanford.edu/~seander/bithacks.html

lxk899

3#不错的。。。

塑料袋

lxk899 发表于 2012-07-05 11:06
3#不错的。。。

我贴的那段代码才是王道啊，不信让@pmerofc来评论一下

huxk

上次貌似有谁发过一个链接，专门讨论这个以及各种优化。

blackuhlan

1. switch(i)
   
2. {
   
3.    case 0x01:
   
4.    case 0x02:
   
5.    case 0x04:
   
6.    case 0x08:
   
7.    case 0x10:
   
8.    ...
   
9.       count = 1;
   
10.    case 0x0003:
    
11.    ...
    
12.       count = 2;
    
13.    ...
    
14. }
    
15. repeat and sum+=count;

复制代码