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

algorithm java bit-manipulation bit

2022-09-01 22:56:16

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

我想了解这里取得了什么成就？我在另一种漂亮的算法中看到了类似的构造，用于检测数字是否是2的幂，例如：n &= (n-1)

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

答案 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 的最低有效位消失。

递减 1 会将最低位翻转，并将每个位翻转到第一位。例如，如果你有1000....0000 -1 = 0111....1111，不管它必须翻转多少位，它都停在那里，让任何其他位保持不变。当你和这个设置了最低位，只有最低位成为n0

答案 2

从数字中减去 1 可切换所有位（从右到左）到最右边的集合位（包括最严格的设置位）。因此，如果我们将一个数字减去 1，并按位 & 与自身一起做，我们取消设置最严格的集合位。通过这种方式，我们可以在循环中从右到左逐个取消设置1。(n & (n-1))

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