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

Question

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

我想在这个讨论中添加一个真正的 O(Log N) 算法，其中 N 是位数（32 或 64）：

int HammingWeight(DWORD dw) {
    dw = (dw & 0x55555555) + ((dw & 0xaaaaaaaa) >>  1);
    dw = (dw & 0x33333333) + ((dw & 0xcccccccc) >>  2);
    dw = (dw & 0x0f0f0f0f) + ((dw & 0xf0f0f0f0) >>  4);
    dw = (dw & 0x00ff00ff) + ((dw & 0xff00ff00) >>  8);
    dw = (dw & 0x0000ffff) + ((dw & 0xffff0000) >> 16);
    return dw;
}