一道老题

doubleelec

赞!!! 楼上聪明,和我目前知道的最佳答案在时间上已不相上下!
比我上面的答案快4-5倍

大家继续
我知的最佳答案不需要额外空间(即数组a)
因此还有改进的余地

lucifer

测试了一下，不算输出的话，用位域至少还可以提高三分之一左右的效率，同时减少空间占用（只有一个int的空间，不需要数组）。不过写起来实在麻烦，ft，主要是int有32位，一个一个写简直...
干脆用程序完成好了，运行以下程序自动生成测试程序(test0.c)并编译运行，用time(1)计时并显示。
[PHP]
#include <stdio.h>
int main(){
        FILE *fp;
        int i;
        fp=fopen("test0.c","w");
        fprintf(fp,"%s","#include <stdio.h>\n");
        fprintf(fp,"%s","#include <stdlib.h>\n");
        fprintf(fp,"%s","typedef struct{\n");
        for(i=0;i<32;i++){
                fprintf(fp,"%s%d%s","\tunsigned int a",i,":1;\n");
        }
        fprintf(fp,"%s","} INT;\n");
        fprintf(fp,"%s","int main(){\n");
        fprintf(fp,"%s","\tint i,j;\n\tunsigned int n,result;\n\tINT intbit;\n");
        fprintf(fp,"%s","\tfor(i=0;i<1000000;i++){\n");
        fprintf(fp,"%s","\t\tn=rand();\n\t\tmemcpy(&intbit,&n,sizeof(n));\n");
        fprintf(fp,"%s","\t\tresult=");
        for(i=0;i<31;i++){
                fprintf(fp,"%s%d%s","intbit.a",i,"+");
        }
        fprintf(fp,"%s","intbit.a31;\n}\n");
        fprintf(fp,"%s","\treturn 0;\n}\n");
        fclose(fp);
        system("gcc -o test0 test0.c");
        system("time ./test0");
        return 0;
}
[/PHP]

lucifer

又改了一把，干脆直接强制类型转换，把一个int的空间也省了，不用内存拷贝，完全原地操作，也就省去了memcpy函数调用的时间，大概比上个版本快1倍。程序如下，一切说明参照上一个版本。
[PHP]
#include <stdio.h>
int main(){
        FILE *fp;
        int i;
        fp=fopen("test0.c","w");
        fprintf(fp,"%s","#include <stdio.h>\n");
        fprintf(fp,"%s","#include <stdlib.h>\n");
        fprintf(fp,"%s","typedef struct{\n");
        for(i=0;i<32;i++){
                fprintf(fp,"%s%d%s","\tunsigned int a",i,":1;\n");
        }
        fprintf(fp,"%s","} INT;\n");
        fprintf(fp,"%s","int main(){\n");
        fprintf(fp,"%s","\tint i,j;\n\tunsigned int n,result;\n\tINT* pintbit;\n");
        fprintf(fp,"%s","\tfor(i=0;i<1000000;i++){\n");
        fprintf(fp,"%s","\t\tn=rand();\n\t\tpintbit=(INT*)&n;\n");
        fprintf(fp,"%s","\t\tresult=");
        for(i=0;i<31;i++){
                fprintf(fp,"%s%d%s","pintbit->a",i,"+");
        }
        fprintf(fp,"%s","pintbit->a31;\n}\n");
        fprintf(fp,"%s","\treturn 0;\n}\n");
        fclose(fp);                                          
        system("gcc -o test0 test0.c");                       
        system("time ./test0");                              
        return 0;      
[/PHP]

lucifer

很大一部分时间估计是消耗在rand()调用上了，这个主要是为了测试方便。实际当然可以去掉。看程序的话，主要的消耗是循环32次做整数加法，这个当然是很快的了。如果没有一个比较有效的数学函数可以从int值直接得到1的位数，那么估计除了直接把所有的结果列出来做switch case（对于int，这个太不现实了），这样应该算是很快的了。我数论不好，计原也是刚好及格，这个问题还要请基础好的牛人指教了。

doubleelec

不错不错,速度达到上面我写的算法的3倍
不过没有到最优哦

我在比较时这样实现你的算法,不反对吧

1. 
   
2. int func(unsigned int num)
   
3. {
   
4. #define intbit (*((INT *)&num))
   
5. 
   
6.         return intbit.a0+intbit.a1+intbit.a2+intbit.a3+intbit.a4+intbit.a5+intbit.a6+intbit.a7
   
7.                +intbit.a8+intbit.a9+intbit.a10+intbit.a11+intbit.a12+intbit.a13+intbit.a14
   
8.                +intbit.a15+intbit.a16+intbit.a17+intbit.a18+intbit.a19+intbit.a20+intbit.a21
   
9.                +intbit.a22+intbit.a23+intbit.a24+intbit.a25+intbit.a26+intbit.a27+intbit.a28
   
10.                +intbit.a29+intbit.a30+intbit.a31;
    
11. }
    

复制代码

lucifer

主要还是写的麻烦，ft。那个位域的定义是必须要写出来的，后面的32个加法也少不了，简直就是折磨啊。比较起来，写个程序事先生成所有的结果，然后直接switch case，也不会更麻烦了。

Sworder

a0到a31是什麽東西？
即使之前有定義，那麽當#define intbit (*((INT *)&num))
時，也應該使用intbit->a0這種形式? 調 用吧？

doubleelec

我帮 lucifer 贴一下那个INT是怎么回事

1. typedef struct{
   
2.         unsigned int a0:1;
   
3.         unsigned int a1:1;
   
4.         unsigned int a2:1;
   
5.         unsigned int a3:1;
   
6.         unsigned int a4:1;
   
7.         unsigned int a5:1;
   
8.         unsigned int a6:1;
   
9.         unsigned int a7:1;
   
10.         unsigned int a8:1;
    
11.         unsigned int a9:1;
    
12.         unsigned int a10:1;
    
13.         unsigned int a11:1;
    
14.         unsigned int a12:1;
    
15.         unsigned int a13:1;
    
16.         unsigned int a14:1;
    
17.         unsigned int a15:1;
    
18.         unsigned int a16:1;
    
19.         unsigned int a17:1;
    
20.         unsigned int a18:1;
    
21.         unsigned int a19:1;
    
22.         unsigned int a20:1;
    
23.         unsigned int a21:1;
    
24.         unsigned int a22:1;
    
25.         unsigned int a23:1;
    
26.         unsigned int a24:1;
    
27.         unsigned int a25:1;
    
28.         unsigned int a26:1;
    
29.         unsigned int a27:1;
    
30.         unsigned int a28:1;
    
31.         unsigned int a29:1;
    
32.         unsigned int a30:1;
    
33.         unsigned int a31:1;
    
34. } INT;
    

复制代码

doubleelec

不过问题是如果unsigned int如果不是32位了,
那个程序就要重新生成
这样一来生成程序的时间也应该算进来了

Sworder

最初由 doubleelec 发表
我帮 lucifer 贴一下那个INT是怎么回事

看明白了，可是哪個:符號是什麽意思呢？
而且即使INT是一個STRUCT?型，那麽調用結構指針變量的内部成員應該使用->符號吧。