求无符号整数二进制数中1的个数

Posted on 2010-09-07 16:17 小火球 阅读(1028) 评论(0)  编辑 收藏 引用 所属分类: Algorithm
今天公司和公司同事一起讨论五子棋的时候,他给我说了他的算法
这里五子棋的算法就不说啦
不过其实他的本质:
就是计算无符号整数中二进制中1的个数的思想
对此我也记录一下
 1 //获取正整数十进制的二进制数表示法
 2 int get2(unsigned int n)
 3 
 4     int nNum = 0;            //保存最后的数(10进制数,2进制格式)
 5     bool bDouble = false;        //是否是双数
 6     if(n%2 == 0)
 7     {
 8         nNum = 1;
 9         bDouble = true;
10     }
11     for(; n > 0;n >>= 1
12     {
13         nNum*=10;
14         nNum+=( n & 1 );
15     }
16     if(bDouble)
17     {
18         nNum -= 1;
19         nNum /= 10;
20     }
21     return nNum; 
22 
23 int main()
24 {
25     cout << get2(257);
26     getchar();
27     return 0
28 
就是将十进制的数以二进制的格式保存(强调“格式”两个字!)

 1 //求正整数二进制中1的个数
 2 int getoneNum(unsigned int n)
 3 {
 4     int i = 0;
 5     for(; n > 0;n >>= 1) 
 6     {
 7         i+=( n & 1 );
 8     }
 9     return i;
10 }
11 //测试输出
12 int main()
13 {
14     cout << getoneNum(253);
15     getchar();
16     return 0; 
17 }
这样的时间复杂度是T(m)=m,取决于二进制数的位数m。如果要求在更短时间内求出,应该如何做呢?
其实大家都喜欢用的方法就是查表法,以空间换取时间。预先把结果存入表中(怎么存就自己写了呗~想一个一个算也是OK的,没有做不到,只有想不到),
然后直接通过下标就可以访问了。
 1 static char tOne[256= {
 2                             1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,
 3                             3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,
 4                             3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,
 5                             3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,
 6                             3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,
 7                             5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,
 8                             3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,
 9                             4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,
10                             3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,
11                             5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,
12                             5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,1
13                         };
14 int GetOneByArray(unsigned int n)
15 {
16     n -= 1;
17     int i;
18     for(i = 0;n > 0;n>>=8)
19     {
20         i += tOne[n&255];
21     }
22     return i;
23 }
24 int main()
25 {
26     cout << GetOneByArray(255);
27     getchar();
28     return 0;
29 }
这样的话,就可以直接读取1-256中1的个数了。在速度上达到的优化,通过tOne[x]就可以得到,连判断都可以不用,速度大大提升。
然后一个整型有4个字节,32位。1-256远远不够,难道要用1-2的32次方的表来保存?还是那句话,没有做不到,只有想不到。
OK,算一下如果要保存2的32次方个数的1的个数,那么这个数组的大小
至少2^32/(256/32)=512MB,哈哈,正是一般内存大小,搞定速度优化,应该还需要内存优化吧。空间换取时间也不能这么高的空间代价吧
于是需要再优化:存放1-256每个数中1的个数,然后分段查询。如上面把32位数分为4段,每段一个字节,所以有一个256大小供查询的表,比512M小太多了吧。
这样就能完成每个int数中二进制1的个数的查询了,站在巨人的肩上学习真好。

话说回来,我同事也用了这种有限的查表法来查询五子棋中某个下子点周围40个空格(当然,一般都小于40个)的状态变化,而状态就是一张表,其实也不多,数据量
比这个要大一些,不过写完的状态大概也只有几十K罢了,我还是喜欢先速度优化再内存优化的方式,因为这样可以让我最大限度的找到我个人认为比较综合有效的解决
方案。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 28, comments - 3, trackbacks - 0, articles - 0

Copyright © 小火球