一道老题

Sworder

嘿嘿。。。刚才又看了看，是兼容的，只不过要小小的修改一下编译选项，指定为强制K&R兼容。爽~~下次做位操作方便多了，哈哈。。。

doubleelec

目前我知道的最佳答案:

1. 
   
2. int func(unsigned int num)
   
3. {
   
4.         int count;
   
5. 
   
6.         for (count=0; num!=0; num=(num-1)&num, count++);
   
7.         return count;
   
8. }
   

复制代码

每次循环去掉最右边的一个 1，所以有多少个 1 就循环多少次。

lucifer

每次循环有一个inc,一个add,一个&，再加上判断，为什么反而会比简单的32个add快呢？把你的测试程序贴一下看看？我的是按照下面的程序，gcc 2.95,编译选项-O0关闭所有优化，用time(1)测试的，位域确实要快一些啊。
[PHP]
#include <stdio.h>
#include <stdlib.h>
int main(){
        unsigned int num,i;
        
        int count;
        for(i=0;i<1000000;i++){
                num=rand();
                for(count=0;num!=0;num=(num-1)&num,count++);
        }
        return 0;
}
[/PHP]
使用位域：
[PHP]
#include <stdio.h>
#include <stdlib.h>
typedef struct{
        unsigned int a0:1;
        unsigned int a1:1;
        unsigned int a2:1;
        unsigned int a3:1;
        unsigned int a4:1;
        unsigned int a5:1;
        unsigned int a6:1;
        unsigned int a7:1;
        unsigned int a8:1;
        unsigned int a9:1;
        unsigned int a10:1;
        unsigned int a11:1;
        unsigned int a12:1;
        unsigned int a13:1;
        unsigned int a14:1;
        unsigned int a15:1;
        unsigned int a16:1;
        unsigned int a17:1;
        unsigned int a18:1;
        unsigned int a19:1;        
        unsigned int a20:1;
        unsigned int a21:1;
        unsigned int a22:1;
        unsigned int a23:1;
        unsigned int a24:1;
        unsigned int a25:1;
        unsigned int a21:1;
        unsigned int a22:1;
        unsigned int a23:1;
        unsigned int a24:1;
        unsigned int a25:1;
        unsigned int a26:1;
        unsigned int a27:1;
        unsigned int a28:1;
        unsigned int a29:1;
        unsigned int a30:1;
        unsigned int a31:1;
} INT;
int main(){
        int i,j;
        unsigned int n,result;
        INT* pintbit;
        for(i=0;i<1000000;i++){
                n=rand();
                pintbit=(INT*)&n;
                result=pintbit->a0+pintbit->a1+pintbit->a2+pintbit->a3+pintbit->a4+pintbit->a5+pintbit->a6+pintbit->a7+pintbit->a8+pintbit->a9+pintbit->a10+pintbit->a11+pintbit->a12+pintbit->a13+pintbit->a14+pintbit->a15+pintbit->a16+pintbit->a17+pintbit->a18+pintbit->a19+pintbit->a20+pintbit->a21+pintbit->a22+pintbit->a23+pintbit->a24+pintbit->a25+pintbit->a26+pintbit->a27+pintbit->a28+pintbit->a29+pintbit->a30+pintbit->a31;
}
        return 0;
}
[/PHP]

doubleelec

1. 
   
2. #include <stdio.h>
   
3. #include <sys/time.h>
   
4. 
   
5. const int LOOP = 1000000;
   
6. 
   
7. int main(int argc, char *argv[])
   
8. {
   
9.         int num, count, i, ms;
   
10.         struct timeval tv1, tv2;
    
11. 
    
12.         gettimeofday(&tv1, NULL);
    
13.         for (i=0; i<LOOP; i++) (void)count1(i);
    
14.         gettimeofday(&tv2, NULL);
    
15.         ms = (tv2.tv_sec - tv1.tv_sec) * 1000 + (tv2.tv_usec - tv1.tv_usec) / 1000;
    
16.         printf("count1 - %d ms.\n", ms);
    
17. 
    
18.         gettimeofday(&tv1, NULL);
    
19.         for (i=0; i<LOOP; i++) (void)count2(i);
    
20.         gettimeofday(&tv2, NULL);
    
21.         ms = (tv2.tv_sec - tv1.tv_sec) * 1000 + (tv2.tv_usec - tv1.tv_usec) / 1000;
    
22.         printf("count2 - %d ms.\n", ms);
    
23. 
    
24.         /* 以下省略 ............... */
    
25. 
    
26.         return 0;
    
27. }
    

复制代码

count1(), count2() 就是我前面说的func()的不同实现

哦，测试程序是有点问题，因为都是 i 比较小的情况下得出的，楼上可以再编个程序测一测

doubleelec

哦，我把count1(i)，count2(i)改成count1(rand())和count2(rand())后，你的程序和上面的答案相比，已经快了一点点

lucifer

i比较小的情况下，确实第一种方法会快一些，毕竟这个时候即使加上循环，也不会有多少次，事实上，只要1的个数在11个以下，方法一的运算次数比方法2少，肯定要快了。测试程序中i取1000000大概就是20位吧，几乎一半以上的情况下都是方法一要快的，结果自然也是方法一快一些。不过在随机情况下，测试足够多次时32位整数1的个数肯定平均要在16左右，这个时候方法2就要快了。总之，如果设需要测试的数字中1的个数是n，那么方法一的复杂度是O(n)，方法二是O(1)，显然平均情况下方法二要好一些。当然，如果是16位以下的数字，肯定是方法一要快了。

doubleelec

方法一的复杂度是O(n)，方法二是O(1)

呵呵，这么说不太合适吧

lucifer

针对特定平台，整数的位数是固定的