40

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

4

3 回答 3

32

该算法经过与设置位一样多的迭代。因此，如果我们有一个仅设置了高位的 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++;
        }
  }
于 2012-09-12T04:10:22.893 回答
8

N 中有 floor(lg(N)) + 1 个有效位——这是一个以 2 为底的对数。n 中 1 的位数最多是这个。所以时间会有渐近上界 O(lg(N)) = O(log(N))。

于 2012-09-12T02:56:28.483 回答
5

这个问题实际上是关于大 O 表示法中 N 的含义，而不是算法的复杂性。

N 表示数据的大小。但是，如果“数据”是单个数字，您需要定义您所理解的数据大小。一个数字的值或它的表示长度。

IMO算法是O（N）。因为在这个二进制表示中计数 1 的问题中，IMO 相关的数据大小是数字表示的长度，而不是它的值，即比特流的长度。显然最坏的情况是所有 1 都进行 N 次迭代。

但是，如果您将 N 的值视为数据的大小，则它的表示具有 log(N) 长度，因此您可以说它是 O(log(N))

PS 只有当您将算法推广到任意高的 Ns 时，大 O 表示法才有意义。在此代码中，N 受 int 大小的限制，因此您可以说它是 O(1)，因为它最多为 64 次循环迭代（对于 64 位整数）

于 2016-11-08T13:45:17.177 回答