计算机科学论坛--(第四期获奖名单公布，最新4节的电子版pdf已开放下载) 预览电子版，写书评，赢取《编程之美—微软技术面试心得》(微软亚洲研究院邹欣等主编)，每周送出3本，机会多多！，欢迎参加由博文视点和本站联合举办的有奖征集书评活动

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

《编程之美》2008年3月底已经上市了。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

看了1章，讲计算字符串相识问题的。内容对我来说有点难（因为我还没认真学习过编程算法），我读了一章，感觉作者写书思路很好，先列举问题，然后写思考步骤，然后给出参考code，最后再引申一下，让读者自己去思考。在国内案例教学书本满天飞的时候，能这样唤醒读书人从另一个角度去思考问题，而且好像还在培养我们解决问题的一种方式。（至少目前指导我的前辈是这么教我的，我想有不少编程的人可能和我一样，拿到问题可能总是急于code(我就有这个毛病)，然后遇到问题gg一下，baidu一下，再不行，就很"心安理得"的去发问了。最后就算解决了，对问题本身的思考是不够的，这样也许是一个解决问题的恶性循环。）

不过这本书的的定位我还不太清楚（也许是我读得太快太少的原因 ^_^），是想通过它唤醒编程人员对算法的重视呢？还是想展示一下编程的魅力？还是想带一般的编程人员进入更高的境界？还是想。。。

如果是象前面的朋友说的，是想以一种诙谐幽默而不失严谨的方式带读者去游览一番算法的领域，那么我个人觉得还不够浅显哦。象我学设计模式，就读了一本我觉得很不错的书。《Head.First设计模式》，这个作者讲解得很浅显，易懂。至少把不少人说得死难的问题，让一般的读者都可以读懂。而我读算法这个第一章，好像没读懂，大脑还是有点混乱。也许是我接触得少的愿意。

最后还是要感谢一下作者，出了一本不错的书给我们品味。也许它就如那苦丁茶，要慢慢品味，才可以品出它的味儿来。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

大致看了一下，本书对问题的描述方式很有趣，解题的思路也很明确。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我第一次听说《编程之美——微软技术面试心得》，是在博客堂2007年会上。当时和邹欣先生坐得不远，他简要地介绍了《编程之美》的内容和写作进度。不久前我在电子科技书店看到此书已经上架，于是借来一阅。
　　此书的优点无须我多言。算法是计算机程序设计的灵魂，是每个计算机专业学生和从业人员必须具备的基础素质之一。微软把一些看似简单，但蕴含深刻内涵的算法题目作为面试的重要内容，是经过深思熟虑的。
　　不过从我个人角度出发，我更希望看到一本讲述与计算机体系结构、操作系统等原理相关的“经典问题”、“面试心得”一类的书籍。就如同《编程之美》第1.1节的内容，从计算机软硬件实现的角度出发，引出问题，进而提出算法。与从数学问题直接引出算法相比，更贴近研发人员的实际。
　　例如竞态条件和死锁、流水线分析和设计等问题，在计算机专业课本中都是生硬的理论和千篇一律的例子。提到读者写者，我们马上就会想到竞态、并发、死锁等问题，但在一个现实的程序或项目中，缺乏经验的编程人员往往不会立刻发现自己遇到的情形恰恰可以套用读者写者模型。从现实程序问题到算法数学原理，需要体系结构模型的过渡。
　　算法和工程是分别是研究和开发人员必备的基本能力，我觉得我的这点期望是二者的交融点。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

    关于《编程之美——微软技术面试心得》之前就看到网站上包括微软公司全球资深副总裁沈向洋和编程界无人不知的潘爱民等很多高手的推荐，看这些评价之后对该书就有非常向往之感了。
    很荣幸在中国XML论坛看到了该书的样章，提前拜读了其中的很多章节，就《求二进制数中1的个数》这一节来说，我想所有程序员应该都写过类似的代码。以前我用到的时候使用其中的解法二：使用位操作，因为现在写程序只要不是太离普就很少考虑复杂度问题。当看到解法三的时候就感觉为之一振，自问还有这种简洁明了思路怎么就没考虑到呢？怀着激动的心情继续往下看，一直到解法五将时间复杂度降到O(1)，那种山外有山人外有人的体会就更加刻骨铭心了。
    我认为该书并不仅是参加面试人员必读的，更广来说从事写程序的人更要字斟句酌的仔细研读，它里面包含了很多技术和思想都是我们必须具备的东西。希望更多的人能读到该书，从中体会并学习到更多的思想、技术和经验。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

从本书的样章内容不难看出，本书通过实际问题例子讲解编程的技巧和艺术。例子都是通过作者精心选择的典型案例，很具代表性。每个例子后面不光是只是答案的描述，还有解题思路的引导，使读者在思考中获得启发，在启发中获得提高。而且往往同一个问题作者提出多种解题思路，并从效率等多个角度进行对比，使读者的思路进一步开阔起来。另外，每个问题之后，作者都会提出一个进一步的开放性问题留给读者思考和练习作为结束，对这个问题感兴趣的读者可以通过这个扩展问题进一步巩固对解题技巧的理解，而不会读了就忘了。

总之，读这本书的时候，不会感到枯燥，会感觉是在和一个经验丰富的编程老手讨论某些有趣的问题。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

算法精妙, 很好很强大！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

金刚坐飞机的问题很有意思，呵呵

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

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

问题很简单，求二进制中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)

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用zellux在2008-4-15 0:29:00的发言：
这里我想针对样章上的一个问题谈谈自己的理解。

问题很简单，求二进制中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时钟周期可以作为一个参考。

这里我再推荐几个解决这个问题的算法，以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)

很好很强大，不过更像是读书笔记而不是书评。


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	152.344ms