问题描述

在求反码时，表达式 x &= (x - 1) 用于把x最右边的值为1的位删除掉。请解释一下这样做的道理。用这一方法重写bitcount函数 ，使之执行得更快一点

问题分解

• 主函数main
• 核心函数 bitcount(x)。我们先来看看书中例子 bitcount的算法实现：

int bitcount(unsigned x)
{
  int b;
  for(b = 0; x != 0; x >>= 1)
  {
    if(x & 1)
      b++;
  }
  return b;
}

从以上代码可知， bitcount 的实现逻辑是根据任何数与1进行位与计算可判断出次数的最右侧是否为1， 根据此原理不断将x右移，妹出现一次1记录一次。 根据题意，我们现在要改造bitcount的实现方式，借用 x &= (x - 1) 。如何理解呢？ 我们知道二进制的特性， 不是0 就是1， 所以x & x - 1操作后的最右边值一定是互反的， 这样，x & （x - 1）的最右边的值一定为0，如此循环后x的最终值为0，循环次数即为x中值为1的个数。

代码实现

#include<stdio.h>
int bitcount(unsigned x);
​
int main()
{
  unsigned x;
  int r;
  x = 3;
  r = bitcount(x);
  printf("The result is: %u \n", r);
  return 0;
}
​
//使用求反码的方式 
int bitcount(unsigned x)
{
  int b;
  for(b = 0; x != 0; b++)
  {
    x &= (x - 1);
  }
  return b;
}

对比两个bitcount函数，我们发现第一个bitcount 中，for每执行一次，比第二个的bitcount 多执行了一次位与(&)操作，因此可以说第二个bitcount的执行速度是更快的。