整数时间复杂度的比特计数算法（Brian Kernighan）

有人可以解释为什么 Brian Kernighan 的算法需要 O(log N) 来计算整数中的设置位 (1)。该算法的简单实现如下（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 has 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++;
        }
  }