硬件设计之 Distributed Arithmetic 一例

下面是一段常见的c代码，用于计算下面这个问题。

问题：求一个32位整数的二进制表示中 1 的数量。

unsigned long CountOnes(unsigned long X) {
    X = (X & 0x55555555) + (X >> 1 & 0x55555555);
    X = (X & 0x33333333) + (X >> 2 & 0x33333333);
    X = (X & 0x0F0F0F0F) + (X >> 4 & 0x0F0F0F0F);
    X = (X & 0x00FF00FF) + (X >> 8 & 0x00FF00FF);
    X = (X & 0x0000FFFF) + (X >> 16 & 0x0000FFFF);
    return(X);
}

它背后的原理是什么呢？这篇文章尝试从硬件设计领域中 Distributed Arithmetic（DA算法）的角度来解释。

首先把这个问题转换成不那么专业的数学语言。

已知一个 32 位正整数

，其中

表示 X 的第 b 位，取值 0 或者 1。该位的权值即 2 的 b 次幂，

。N 在此例中等于 32。

求 X 的二进制表示中的 1 的数量，即

。

上面 c 代码函数中的第一步

    X = (X & 0x55555555) + (X >> 1 & 0x55555555);

的结果可以用下式表示，

其中，b 的取值是 0 到 15。它的含义就是每相邻两个 bit 中含有的 1 的个数，这 16 个个数是单独体现在每两个 bit 组成的整数中，把这 16 个两 bit 数组合在一起，1 的个数的含义就模糊不清了，因为每个两 bit 数都用 2 的 2b 次幂加权了。分开看才会清楚，这也是这段 c 代码容易使人困惑的主要原因。

直接考虑用硬件实现的时候，不必用 1 个 32 bit 宽的加法器，而是用 16 个 1 bit 加法器并行计算。这就是 DA 算法的分布式计算特点。

上面 c 代码函数中的第二步

    X = (X & 0x33333333) + (X >> 2 & 0x33333333);

的结果可以用下式表示，

其中，b 的取值是 0 到 7。它的含义就是每四个 bit 中含有的 1 的个数，这 8 个个数是单独体现在每四个 bit 组成的整数中，同样这 8 个四 bit 数组合在一起，含义也是隐藏起来的，因为每个四 bit 数都用 2 的 4b 次幂加权了。同样也是分开看才清楚。

类似的第三步可以用下式表示，

其中，b 的取值是 0 到 3。

第四步可以用下式表示，

其中，b 的取值是 0 到 1。

第五步，及最后一步可以表示为，

其中，b 的取值只有 0，即上式可以简化为

从这里就可以看到，此时 X 的取值，就是原来的 32 位整数 X 的二进制表示中的 1 的个数了。

看到这里，读者朋友们对这几句“奇技淫巧”般的代码背后的数学原理应该有所了解了吧。不过这种代码也并不只是在面试中为难面试者的，它还真是用来解决实际问题的。

比如，编码理论中经常提到的计算一个编码符号的 hamming weight，就是这个编码符号相对于全零编码符号的 hamming distance，二进制情况下也就是这个编码符号中 1 的个数。