请解释Kernighan位计数算法背后的逻辑

小编典典

algorithm

在以整数时间复杂度阅读[位计数算法（BrianKernighan）后，直接提出该问题。有问题的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");
}

阅读 295

2020-07-28

共1个答案

小编典典

在调试器中逐步执行代码对我有帮助。

如果从

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的最低有效位消失的方式减小该值。

递减一位将最低位翻转，最高位则翻转至第一位。例如，如果您有1000..0000 -1 = 0111 ....
1111，则无论要翻转多少位，它都会停在那儿，而所有其他位都保持不变。当您n设置最低位并且只有最低位时0

2020-07-28