1

这是一小段程序（14 行程序），它计算一个 number 中设置的位数。

输入-输出--> 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;
}

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

4

1 回答 1

12

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）。

...依此类推，直到你得到一个与你需要的位数一样宽的结果。

我建议您使用上面的二进制掩码在纸上手动尝试一些数字。然后您可能会对该代码所表达的算法有所了解。

于 2013-11-06T06:04:29.667 回答