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

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

该算法经过与设置位一样多的迭代。因此，如果我们有一个只设置了高位的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++;        }  }