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

在以整数时间复杂度读取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

Answer 2

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

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

资料来源： Brian Kernighan的算法