问题很简单，求二进制中1的个数。对于一个字节（8bit）的变量，求其二进制表示中”1”的个数，要求算法的执行效率尽可能的高。 先来看看样章上给出的几个算法：

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

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

1
2
3
4
5
6
7
8
9

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

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

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

1
2
3
4
5

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

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

好了，这就是样章上给出的四种方案，下面谈谈我的看法。 首先是对算法的衡量上，复杂度真的是唯一的标准吗？尤其对于这种数据规模给定，而且很小的情况下，复杂度其实是个比较次要的因素。 查表法的复杂度为O(1)，我用解法一，循环八次固定，复杂度也是O(1)。至于数据规模变大，变成32位整型，那查表法自然也不合适了。 其次，我觉得既然是这样一个很小的操作，衡量的尺度也必然要小，CPU时钟周期可以作为一个参考。 解法一里有若干次整数加法，若干次整数除法（一般的编译器都能把它优化成位移），还有几个循环分支判断，几个奇偶性判断（这个比较耗时间，根据CSAPP上的数据，一般一个branch penalty得耗掉14个左右的cycle），加起来大概几十个cycle吧。 再看解法四，查表法看似一次地址计算就能解决，但实际上这里用到一个访存操作，而且第一次访存的时候很有可能那个数组不在cache里，这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle（因为要访问内存）。所以对于这种“小操作”，这个算法的性能其实是很差的。 这里我再推荐几个解决这个问题的算法，以32位无符号整型为例。

1
2
3
4
5
6
7
8

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算法

1
2
3
4
5
6
7
8
9
10
11

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的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。 因为2⁶ = 64，也就是说 x₀ + x₁ * 64 + x₂ * 64 * 64 = x₀ + x₁ + x₂ (mod 63)，这里的等号表示同余。 这个程序只需要十条左右指令，而且不访存，速度很快。 由此可见，衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。 关于后面的两道扩展问题，问题一是问32位整型如何处理，这个上面已经讲了。 问题二是给定两个整数A和B，问A和B有多少位是不同的。 这个问题其实就是数1问题多了一个步骤，只要先算出A和B的异或结果，然后求这个值中1的个数就行了。