有人可以解释为什么Brian Kernighan的算法采用O（log N）来计数整数中的设置位（1s）。下面是该算法的简单实现（在JAVA中）
int count_set_bits(int n){ int count = 0; while(n != 0){ n &= (n-1); count++; } return count; }
我了解如何通过将最右边的设置位一一清除直到变为0来了解它的工作原理，但是我只是不知道我们如何获得O（log N）。
该算法经过与设置位一样多的迭代。因此，如果我们有一个只设置了高位的32位字，那么它将只循环一次。在最坏的情况下，它将每位通过一次。整数n有log(n)位，因此最坏的情况是O(log(n))。这是在重要位（双关语意味）处注释的代码：
n
log(n)
O(log(n))
int count_set_bits(int n){ int count = 0; // count accumulates the total bits set while(n != 0){ n &= (n-1); // clear the least significant bit set count++; } }
