比特计算算法(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 只有当您将算法推广到任意高的 Ns 时，大 O 符号才有意义。在这段代码中，N 受整数大小的限制，因此您可以说它是 O(1)，因为它最多需要 64 次循环迭代（对于 64 位整数）