代码之美：寻找快速的种群计数 读后感

问题：求一个32位的字中bit 1的个数。

分析：我们大多数人的第一想法，大致如下（也许略有不同）。

int cnt = 0;
for (int k = 0; k < 32; ++k)
{
    if (x&1) ++cnt;
    x >>= 1;
}

作者分析和上述代码的运行时执行的RISC指令总数，大约208条，他为什么要分析这个呢？

    那么上述代码在逻辑和解题思路不变的情况下，仅仅在编码方面还能有什么改进呢？关键是在条件判断上做文章，利用C的0为false，其他为true，尽量减少变量，尽量减少比较次数。请看如下代码:

int cnt = 0;
while (x)
{
   cnt += (x&1);
   x >>= 1;
}

此时指令条数大约变为128-160左右，说明研究使用的语言被编译成的目标码的条数，对于编写高度精简、高效、优雅的代码大有裨益。

   之后的解法，逻辑方向改变了，利用了x&(x-1)将x的最低的bit 1清零，这个知识性比较强，类似的有x|(x+1)将x的最有的bit 0置为一。至于你想没想到，反正我是没想到。如果利用x&(x+1)，代码类似如下：

int cnt = 0;
while (x)
{
  ++cnt;
  x &= (x-1);
}

如果利用x|(x+1)的话，代码大致如下：

int cnt = 32;
//cnt = 0; x = ~x;
while (x+1)
{
  --cnt;
  x |= (x+1);
}

指令条数大约为4.5 * N,N为字中bit 1的个数。

    此外，对于以上代码还可以继续优化，例如对于例程1，可以将循环展开；另外可以对于单个字节可以表示的256个数中的bit 1的个数以表的形式列出，然后查表即可，效率很高。代码大致如下：

static char table[] = {0,1,1,2,. . ., 8};
cnt = table[x&0xFF]+table[x&0xFF00]+
      table[x&0xFF0000]+table[x&0xFF000000];