algorithm - 整数时间复杂度的位计数算法 (Brian Kernighan)

Question

有人可以解释为什么 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)。

Answer 1

此算法会经历与设置位一样多的迭代。所以如果我们有一个只设置了高位的 32 位字，那么它只会通过循环一次。在最坏的情况下，它会每位通过一次。一个整数 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++;
        }
  }