这个C程序背后的逻辑是什么？

Question

这是一小段程序(14行程序),它计算一个数字中设置的位数.

输入 - 输出 - > 0 - > 0(0000000),5 - > 2(0000101),7 - > 3(0000111)

int CountBits (unsigned int x)
{
  static unsigned int mask[] = { 0x55555555,
      0x33333333,
      0x0F0F0F0F,
      0x00FF00FF,
      0x0000FFFF
      } ;

      int i ;
      int shift ; /* Number of positions to shift to right*/
      for (i =0, shift =1; i < 5; i ++, shift *= 2)
              x = (x & mask[i ])+ ( ( x >> shift) & mask[i]);
      return x;
}

有人可以解释这里使用的算法/为什么这有效？

Answer 1

Ian Ashdown的这篇文章更详细地解释了它:

Freed的数字是序列的成员,其中序列的第N个数本身是从2*N 1的右到左的无限序列,接着是2*N 0,接着是2**N 1,依此类推.初始数字是:

...0101010101010101
...0011001100110011
...0000111100001111
...0000000011111111
...

对于16位的字大小,我们有四个"B常数":

B[1] = 0101010101010101
B[2] = 0011001100110011
B[3] = 0000111100001111
B[4] = 0000000011111111

这就是那些数字mask[],例如.0x55555555是位模式的十六进制表示1010101010101010101010101010101.

算法本身就是这样做的:

1. 将相邻位解释为数字(0或1)并添加它们.结果是可以用两位表示的数字(即0到3).
2. 将相邻的位对解释为数字(0到3)并添加它们.结果可以用四位表示(即0到15).
3. 将相邻的4位组解释为数字(0到15)并添加它们.结果可以用8位表示(即0到255).

...等等,直到你得到的结果与你需要的多个位一样宽.

我建议你手工使用上面的二进制掩码用一些数字在纸上试一试.然后,您可能会感觉到该代码所表达的算法.