通读 Bits counting algorithm (Brian Kernighan) in an integer time complexity后直接出现此问题.有问题的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");
}
最佳答案
在调试器中单步调试代码对我有帮助。
如果你开始
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 无论它必须翻转多少位，它都会停在那里，而其他任何位都保持不变。当你和 this 用 n 设置最低位并且只有最低位变成 0
关于java - 请解释一下 Kernighan 的比特计数算法背后的逻辑，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12383002/