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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

回答：

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

以上是 整数时间复杂度的位计数算法（Brian Kernighan） 的全部内容， 来源链接： utcz.com/qa/410066.html

回到顶部