问题很简单，给定一个 8 位整型，要求写程序计算这个数的二进制表示中 1 的个数，要求算法的执行效率尽可能的高。

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

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

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

int Count(int v)
{
    int num = 0;
    while (v) {
        num += v & 0x01;
        v >>= 1;
    }
    return num;
}

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

解法四，查表法，因为 8 位整型的范围是 0 - 255，可以直接把结果保存在一张表中，然后查表就行。书上强调这个算法的复杂度为 O(1)。

int countTable[256] = { 0, 1, 1, 2, 1, ...,  7, 7, 8 };

int Count(int v) {
    return countTable[v];
}

好了，这就是样章上给出的四种方案，下面谈谈我的看法。

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

查表法的复杂度为 O(1)，用解法一，循环次数不会超过 8 次，所以时间复杂度也是 O(1)。至于数据规模变大，例如变成 32 位整型，那查表法自然也不合适了。

其次，既然是一个执行时间很短的操作，衡量的尺度也必然要小，CPU 时钟周期可以作为参考单位。

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

再看解法四，查表法看似一次地址计算就能解决，但实际上它用到了查表访存操作，而访存的时候很有可能那个数组不在 cache 里，需要从内存重新读取。这样一个 cache miss 导致的后果可能就是耗去几十甚至上百个 cycle（因为要访问内存）。所以实际情况中这个算法的性能是很差的。

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

int Count(unsigned x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。

还有一个更巧妙的 HAKMEM 算法

int Count(unsigned x) {
   unsigned n;

   n = (x >> 1) & 033333333333;
   x = x - n;
   n = (n >> 1) & 033333333333;
   x = x - n;
   x = (x + (x >> 3)) & 030707070707;
   x = x % 63;
   return x;
}

用了二分法，先将二进制表示分组，每三位一组，并求出每组中 1 的个数。然后相邻两组归并，分组变成了每六位一组。最后除 63 取余得到结果。因为 26 = 64，也就是说 x0 + x1 * 64 + x2 * 64 * 64 = x0 + x1 + x2 (mod 63) （这里的等号表示同余）。

这个程序只需要十条左右指令，虽然有除法指令，但是由于不访存，速度还是会比较快。

综上，衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。关于书后的两道扩展问题，问题一是问 32 位整型如何处理，这个上面已经讲了。问题二是给定两个整数 A 和 B，问 A 和 B 有多少位是不同的。这个问题可以规约到数 1 问题——只要先算出 A 和 B 的异或结果，然后求这个值中 1 的个数就行了。