在以整数时间复杂度阅读[位计数算法（BrianKernighan）后，直接提出该问题。有问题的Java代码是
int count_set_bits(int n) { int count = 0; while(n != 0) { n &= (n-1); count++; } }
我想了解一下n &= (n-1)在这里取得了什么成就？我在另一种用于检测数字是否为2的幂的漂亮算法中看到了类似的构造：
n &= (n-1)
if(n & (n-1) == 0) { System.out.println("The number is a power of 2"); }
在调试器中逐步执行代码对我有帮助。
如果从
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
n
0
