一道老题

doubleelec

int func(unsigned int number);
函数func的功能是计算number(看成一个二进制序列)中有多少个"1",
请实现这个函数.

一道老题了,可能很多人知道答案,
但觉得还有点搞头,贴出来让大家共赏

lanche

一般都用移位并相加吧，我则是这么想的，将这个number存入位域结构变量中，然后直接计算八个位域的和，要花费掉内存中拷贝一个字节和八次加法的时间。

doubleelec

写出源码看看?反正就几行代码

不妨做出几种不同的答案然后比较一下运行时间,
我让这个函数取参数从1到1000000循环运行,
测出目前已知的最好算法比"移位相加"平均快4到5倍
如果我说的"移位相加"和你说的是一回事的话

lucifer

不是一回事。直接用位域的话，到是可以省去循环计数，（写起来的麻烦不考虑），不过要计算int不是char，就要32次加法了。整数加法算起来到是不费时间。如果是char，到是可以考虑直接把所有可能列举一下，一个switch case就搞定了，肯定很快。int的话，这么做就太麻烦了。

tomcat5

#include <stdio.h>

int func(unsigned int number);

int main(void)
{
int i;
for(i=1;i<2147483648;i++)
{
printf("the number is %d\n",func(i));
}
getchar();
}

int func(unsigned int number)
{
int i=0;
int t=0;
int flag;
for(t=0;t<32;t++)
{
flag=0;
number=number<<1;
if((number&2147483648)==2147483648)
{
i++;
flag=1;
}
else
flag=0;
if(flag==1)
printf("1");
else if(i>0&&flag!=1&&t<31)
printf("0");
}
printf("\n");
return i;
}

doubleelec

一点意见
1.  for(t=0;t<32;t++)虽然你知道你正使用的系统上unsigned int是32位的,
     但这样写会使程序的可移植性降低
2.  number=number<<1;
     if((number&2147483648)==2147483648)
     第一句执行完后,number的最左边一位是什么就不知道了,
     那么你的统计结果是不是漏了一位?

提示:如果一定要循环 sizeof(number) * 8 次,每个人写出来得代码
会大同小异,不能显著提高程序的效率

doubleelec

我做的一个低效率的答案

1. 
   
2. int func(unsigned int num)
   
3. {
   
4.         int count = 0;
   
5. 
   
6.         while(num)
   
7.         {
   
8.                 if (num % 2) count++;
   
9.                 num >>= 1;
   
10.         }
    
11. 
    
12.         return count;
    
13. }
    

复制代码

tomcat5

呵呵，楼上的兄弟，谦虚啊！好像你这个快很多。不错，不错，我最近才复习c语言，看到这个，就自己写了一个，其实呢？是调试出来的，感觉好像是对的。针对我的平台，试了好多数字，都是对的。

tomcat5

谢谢楼上的意见，呵呵，看来写一个程序要考虑多方面的情况啊

libinary

这个程序主要的时间都耗在输出上了，几个程序都看不出来多少区别，如果要比较的话应该去掉输出。

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. #define COUNT 1000000
   
6. 
   
7. int a[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
   
8. 
   
9. int func(unsigned int);
   
10. 
    
11. int
    
12. main(void)
    
13. {
    
14.   int i;
    
15.   
    
16.   for(i = 1; i < COUNT; i++){
    
17.     printf("%2d ", func(rand()));
    
18.     if(i % 20 == 19)
    
19.       printf("\n");
    
20.   }
    
21. }
    
22. 
    
23. int
    
24. func(unsigned int num)
    
25. {
    
26.   int c = 0;
    
27.   
    
28.   while(num){
    
29.     c += a[num & 0xf];
    
30.     num >>= 4;
    
31.   }
    
32.   return c;
    
33. }
    

复制代码