Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

《编程之美》上的一道题目的讨论

Posted on 2008-04-15 00:23 ZelluX 阅读(4050) 评论(8)  编辑  收藏 所属分类: Algorithm

计算机科学论坛最近举办了一个阅读样章,提交书评的活动,具体内容请见http://www.ieee.org.cn/dispbbs.asp?boardID=42&ID=61162

这里我想针对样章上的一个问题谈谈自己的理解。

问题很简单,求二进制中1的个数。对于一个字节(8bit)的变量,求其二进制表示中"1"的个数,要求算法的执行效率尽可能的高。

先来看看样章上给出的几个算法:

解法一,每次除二,看是否为奇数,是的话就累计加一,最后这个结果就是二进制表示中1的个数。

解法二,同样用到一个循环,只是里面的操作用位移操作简化了。

   1:  int Count(int v)  
   2:  {  
   3:      int num = 0;
   4:      while (v) {  
   5:          num += v & 0x01;  
   6:          v >>= 1;  
   7:      }  
   8:      return num;  
   9:  }

解法三,用到一个巧妙的与操作,v & (v -1 )每次能消去二进制表示中最后一位1,利用这个技巧可以减少一定的循环次数。

解法四,查表法,因为只有数据8bit,直接建一张表,包含各个数中1的个数,然后查表就行。复杂度O(1)。

   1:  int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };  
   2:     
   3:  int Count(int v) {  
   4:      return countTable[v];  
   5:  }
  
好了,这就是样章上给出的四种方案,下面谈谈我的看法。

首先是对算法的衡量上,复杂度真的是唯一的标准吗?尤其对于这种数据规模给定,而且很小的情况下,复杂度其实是个比较次要的因素。

查表法的复杂度为O(1),我用解法一,循环八次固定,复杂度也是O(1)。至于数据规模变大,变成32位整型,那查表法自然也不合适了。

其次,我觉得既然是这样一个很小的操作,衡量的尺度也必然要小,CPU时钟周期可以作为一个参考。

解法一里有若干次整数加法,若干次整数除法(一般的编译器都能把它优化成位移),还有几个循环分支判断,几个奇偶性判断(这个比较耗时间,根据CSAPP上的数据,一般一个branch penalty得耗掉14个左右的cycle),加起来大概几十个cycle吧。

再看解法四,查表法看似一次地址计算就能解决,但实际上这里用到一个访存操作,而且第一次访存的时候很有可能那个数组不在cache里,这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle(因为要访问内存)。所以对于这种“小操作”,这个算法的性能其实是很差的。

这里我再推荐几个解决这个问题的算法,以32位无符号整型为例。

   1:  int Count(unsigned x) {  
   2:     x = x - ((x >> 1) & 0x55555555);   
   3:     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);   
   4:     x = (x + (x >> 4)) & 0x0F0F0F0F;   
   5:     x = x + (x >> 8);   
   6:     x = x + (x >> 16);   
   7:     return x & 0x0000003F;   
   8:  }
  
这里用的是二分法,两两一组相加,之后四个四个一组相加,接着八个八个,最后就得到各位之和了。

还有一个更巧妙的HAKMEM算法

   1:  int Count(unsigned x) {
   2:     unsigned n;   
   3:     
   4:     n = (x >> 1) & 033333333333;   
   5:     x = x - n;  
   6:     n = (n >> 1) & 033333333333;  
   7:     x = x - n;   
   8:     x = (x + (x >> 3)) & 030707070707;  
   9:     x = modu(x, 63); 
   10:     return x;  
   11:  }
  
首先是将二进制各位三个一组,求出每组中1的个数,然后相邻两组归并,得到六个一组的1的个数,最后很巧妙的用除63取余得到了结果。

因为2^6 = 64,也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63),这里的等号表示同余。

这个程序只需要十条左右指令,而且不访存,速度很快。

由此可见,衡量一个算法实际效果不单要看复杂度,还要结合其他情况具体分析。

关于后面的两道扩展问题,问题一是问32位整型如何处理,这个上面已经讲了。

问题二是给定两个整数A和B,问A和B有多少位是不同的。

这个问题其实就是数1问题多了一个步骤,只要先算出A和B的异或结果,然后求这个值中1的个数就行了。

总体看来这本书还是很不错的,比较喜欢里面针对一个问题提出不同算法并不断改进的风格。这里提出一点个人的理解,望大家指正 ;-)

(by ZelluX   http://www.blogjava.net/zellux)


评论

# re: 《编程之美》上的一道题目的讨论  回复  更多评论   

2008-04-15 02:15 by Lee.MaRS
mod是一个异常慢的操作……

# re: 《编程之美》上的一道题目的讨论  回复  更多评论   

2008-04-15 02:25 by stanleyxu
You cannot judge the performance of an algorithm by calculating its time complexity. You should first convert code into opcode and then calculate. This is more fairer.

# re: 《编程之美》上的一道题目的讨论  回复  更多评论   

2008-04-15 08:37 by ZelluX
@Lee.MaRS
十几个cycle应该够了吧?

# re: 《编程之美》上的一道题目的讨论  回复  更多评论   

2008-04-15 08:39 by ZelluX
@stanleyxu
所以我主要看的是cycle数么。。。

# re: 《编程之美》上的一道题目的讨论  回复  更多评论   

2008-04-15 09:11 by 如坐春风
>>总体看来这本书还是很不错的,比较喜欢里面针对一个问题提出不同算法并不断改进的风格。

有空找来看看.

# re: 《编程之美》上的一道题目的讨论  回复  更多评论   

2008-04-15 11:15 by tumi
博主,你好,我是《编程之美》的营销编辑,你的这篇文章被我转载到博文官方博客了http://blog.csdn.net/bvbook/archive/2008/04/15/2292823.aspx
期待读到你更多的感想。我的联系方式是:tumi711@gmail.com msn:julybluekid@hotmail.com

# re: 《编程之美》上的一道题目的讨论  回复  更多评论   

2008-04-16 23:33 by luohandsome
思考得真周到!

# re: 《编程之美》上的一道题目的讨论  回复  更多评论   

2008-04-21 12:39 by W3China
恭喜你的书评入选 电子工业出版社博文视点与W3China联合举办的“看独家样章,写书评,赢取《编程之美—微软技术面试心得》”第一期优秀书评。请速前往本站领奖。

只有注册用户登录后才能发表评论。


网站导航: