请解释Kernighan位计算算法的逻辑

2018-06-25 22:17:47

在以整数时间复杂度阅读比特计数算法（Brian Kernighan）之后，此问题直接遵循。有问题的Java代码是

int count_set_bits(int n) {
  int count = 0;
    while(n != 0) {
      n &= (n-1);
      count++;
    }
 }

我想知道n &= (n-1)在这里实现了什么？我在另一个漂亮的算法中看到了类似的构造，用于检测数是否是2的幂，如：

if(n & (n-1) == 0) {
    System.out.println("The number is a power of 2");
}

在调试器中浏览代码帮助了我。

如果你开始

n = 1010101 & n-1=1010100 => 1010100
n = 1010100 & n-1=1010011 => 1010000
n = 1010000 & n-1=1001111 => 1000000
n = 1000000 & n-1=0111111 => 0000000

所以这个迭代4次。每次迭代以这样的方式递减该值，使得设置为1的最低有效位消失。

递减1将翻转最低位，并且每一位翻到第一位。例如，如果你有1000 .... 0000 -1 = 0111 ... 1111，不管它有多少位需要翻转，它在那里停止，所有其他位都不变。当你和这个n设置最低位并且只有最低位变为0

从数字中减1可以切换所有位（从右到左）直到最右边的位（包括最右边的位）。所以，如果我们用1减去一个数字并且按位与它自己(n & (n-1)) ，则我们将最右边的位置位。这样我们可以在循环中从右到左逐个取消1。

循环迭代的次数等于设置位的数量。

资料来源：Brian Kernighan的算法

链接地址: http://www.djcxy.com/p/72541.html