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

Question

在以整数时间复杂度读取Bits计数算法(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");
}

Answer 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