java - 请解释一下 Kernighan 的比特计数算法背后的逻辑

Question

在阅读整数时间复杂度的位计数算法（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");
}

score 37 · Accepted Answer

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

如果你从

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，无论它必须翻转多少位，它都会停在那里，而其他任何位都保持不变。当您和 thisn设置了最低位并且只有最低位变为0

score 2 · Accepted Answer

从数字中减去 1 会切换所有位（从右到左）直到最右边的设置位（包括最右边的设置位）。因此，如果我们将一个数字减 1 并对其自身进行按位 & (n & (n-1))，我们将取消设置最右边的设置位。这样我们就可以在循环中从右到左一个一个地取消设置1。

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

2 回答 2