Aiur

zellux 的博客

《编程之美》一个二进制趣题的讨论

Permalink

问题很简单,给定一个 8 位整型,要求写程序计算这个数的二进制表示中 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,利用这个技巧可以减少一定的循环次数。

解法四,查表法,因为 8 位整型的范围是 0 - 255,可以直接把结果保存在一张表中,然后查表就行。书上强调这个算法的复杂度为 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),用解法一,循环次数不会超过 8 次,所以时间复杂度也是 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 的个数。然后相邻两组归并,分组变成了每六位一组。最后除 63 取余得到结果。因为 26 = 64,也就是说 x0 + x1 * 64 + x2 * 64 * 64 = x0 + x1 + x2 (mod 63) (这里的等号表示同余)。

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

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

评论