有人可以解释为什么布赖恩Kernighan的算法需要O（日志N）在一个整数设置位计​​数（1秒）。一个简单的实现这个算法是低于（JAVA中）

Can someone explains why Brian Kernighan's algorithm takes O(log N) to count set bits (1s) in an integer. A simple implementation of this algorithm is below (in JAVA)

int count_set_bits(int n){
    int count = 0;
    while(n != 0){
        n &= (n-1);
        count++;
    }
}

我理解它是如何工作通过清除最右边的设置位一个接一个，直到它变成0，但我不知道我们如何为O（log N）。​​

I understand how it works by clearing the rightmost set bit one by one until it becomes 0, but I just don't know how we get O(log N).

推荐答案

这个算法经过尽可能多的迭代有设置位。因此，如果我们有只与高比特集的32位的字，那么它将仅通过循环去一次。在最坏的情况下，它会通过每比特一次。一个整数 N 的的log（n）位，因此最坏的情况是 O（日志（N））。这是你的code注释的重要位（双关语意）：

This algorithm goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop. In the worst case, it will pass once per bit. An integer n has log(n) bits, hence the worst case is O(log(n)). Here's your code annotated at the important bits (pun intended):

  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++;
        }
  }