下面是一段常见的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 的个数。