求二进制中的 ‘1’ 的个数-凯发app官方网站

凯发app官方网站-凯发k8官网下载客户端中心 | | 凯发app官方网站-凯发k8官网下载客户端中心
  • 博客访问: 301088
  • 博文数量: 33
  • 博客积分: 132
  • 博客等级: 入伍新兵
  • 技术积分: 1002
  • 用 户 组: 普通用户
  • 注册时间: 2012-09-16 22:24
个人简介

学习计算机科学与技术专业,喜欢计算机,喜欢linux,喜欢编程

文章存档

2014年(7)

2013年(12)

2012年(14)

相关博文
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·
  • ·

分类: c/c

2013-10-14 18:33:04

这是我最近看《编程之美》那本书上的一个例子,和大家分享下我的理解。

这个题目其实不难,但是这个题目要求算法的执行效率尽可能高。什么才是高效率的算法呢?很模糊,你的算法也许还是会被更高效的算法给 pass掉。下面是我对这道题算法的总结,不能说是很高效的,但是也算不错了。


解法一:我们都知道,用这个数数以一个 2 ,原来的数字将会减少一个 0 。如果在除的过程中  有余数,那么就表示当前位置有一个 1 。

以 100011010 为例:

第一次除以 2 时,商为 10001101,余数为 0;

第二次除以 2 时,商为 1000110 ,余数为 1;

利用这个特点我们可以编写大概的代码如下:

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

这种算法的效率怎么样呢?

解法二:通过上面的算法,我们可以看出,利用向右移位操作也可以实现这个过程,当然了,位运算的效率更高些。代码实现如下:


  1. int count(bype v)
  2. {
  3.     int num = 0;
  4.     while (v)
  5.     {
  6.         num = v & 0x01;
  7.         v >>= 1;
  8.     }
  9.     return num;
  10. }
你还能想到更好的算法吗?


解法三:位运算的效率明显高于解法一,但是采用位操作,时间复杂度还是o(logv)  。logv是二进制数的位数。如果有办法让算法的复杂度只与“1”的个数有关,那么时间复杂度应该会降低一些。

为了简化这个问题,我们考虑只有一个“1”的情况,例如:00100000。

如何判断给定的二进制数里面有且只有一个“1”呢?可以通过判断这个数是否是 2 的整数次幂来实现。如果只和这一个“1”进行判断,结果为 0 或者 1 。所以如果进行这个操作后的结果为 0 ,00100000可以和00011111进行“与”操作。     

这个算法又怎样设计呢?


  1. int count(byte v)
  2. {
  3.     int num = 0;
  4.     while (v)
  5.     {
  6.         v &= (v - 1);
  7.         num;
  8.     }
  9.     return num;
  10. }
这个方法使得仅有一个 1 的情况仅进行一次判断就可得出。所以算是对上面的算法进行了优化,提高了效率。这个算法的复杂度降低到了o(m),其中 m 是 v 中 1 的个数。       
               


解法四:当然了,如果你要是只针对八位进制的数据我们可以用分支法来实现,具体代码如下:


  1. int count(byte v)
  2. {
  3.     int num = 0;
  4.     switch (v)
  5.     {
  6.         case 0x0:
  7.             num = 0;
  8.             break;
  9.         case 0x1:
  10.         case 0x2:
  11.         case 0x4:
  12.         case 0x8:
  13.         case 0x10:
  14.         case 0x20:
  15.         case 0x40:
  16.         case 0x80:
  17.             num = 1;
  18.             break;
  19.         case 0x3:
  20.         case 0x6:
  21.         case 0xc:
  22.         case 0x18:
  23.         case 0x30:
  24.         case 0x60:
  25.         case 0xc0:
  26.             num = 2;
  27.             break;
  28.             //... (这块还要继续写下去)
  29.     }
  30.     return num;
  31. }
这个算法不算是很好,效率不是很好而且还要写很多东西,但是它给我们了一种思路就是用空间换时间。你可以写一个含有 256个元素的数字,把每个值对应的数中含有 1 的个数都当做它的元素值就好了,这种方法直接就可以得出结果。当然确定是浪费空间,代码量大。


解法五:这个解法效率也很好,是在看了我同学的博客后写的。代码如下:


  1. int bit_count(unsigned int x )
  2. {
  3.   static unsigned int mask[] = { 0x55555555,
  4.                                  0x33333333,
  5.                                  0x0f0f0f0f,
  6.                                  0x00ff00ff,
  7.                                  0x0000ffff };
  8.   int i;
  9.   int shift; /* number of positions to shift to right */
  10.           
  11.   for( i=0, shift=1; i < 5; i, shift *= 2 )
  12.     x = (x & mask[i]) ( (x >> shift) & mask[i] );
  13.   return x;
  14. }

以上是一个比较小的问题,但是对问题的深入思考可以给我们很多启示。                       
博文链接是:


阅读(1982) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
")); function link(t){ var href= $(t).attr('href'); href ="?url=" encodeuricomponent(location.href); $(t).attr('href',href); //setcookie("returnouturl", location.href, 60, "/"); }
网站地图