整数时间复杂度下的比特计数算法（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)。

- peter

---

n用log(n)位表示。(反过来，k位可以表示高达2^k的数字。)检查每个位需要恒定时间，因此我们最终得到log(n)时间。 - user684934

在Java中，应该使用while(n!=0)。否则负数将无法正确计数。 - Nathan Andrew Mullenax

我明白了，刚刚纠正了它。 - peter

http://softwareengineering.stackexchange.com/questions/304876/explanation-to-why-counting-bits-set-brian-kernighans-way-works - OhadR

如果N是位数，则为O(N)，但如果N是n，则为O(log N)。 - nonopolarity

Answer 1

这个算法会遍历二进制表示中所有为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++;
        }
  }

- PengOne

---

当你说'n有log(n)位'时，你是指'有效位'还是只是位。我会假设用于表示整数的总位数对于给定平台保持不变。 - Quest Monger

我认为即使我们逐个比特位计算，时间复杂度仍然是O(log n)。 Brian Kernighan 算法只改进了平均情况或最优情况：如果我们假设一半的比特位都是 1，那么循环次数就会减少一半... 如果这个数字只有一个置位的比特位，那么 Brian Kernighan 算法只需要循环一次，而不像逐个比特位计算需要循环 32 或 64 次（例如：如果第 6 位是置位的，则循环 6 次直到第 6 位变成 0）。如果只有两个位是 1，那么 Brian Kernighan 算法只需循环两次。 - nonopolarity

@太极者无极而生更紧凑地表达：天真的解决方案是theta(log n)，而Kernighan的解决方案是O(log n)。 - andreee

Answer 2

N 的二进制表示中有 floor(lg(N)) + 1 个重要位 -- 这是一个以2为底的对数。N 中的 1 位的数量不会超过这个值。因此，时间复杂度的上界为 O(lg(N)) = O(log(N))。

- The_Sympathizer

Answer 3

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

N表示数据的大小。但是在数据为单个数字的情况下，您需要定义您所理解的数据大小。数字的值或其表示的长度。

我认为该算法的复杂度为O(N)。因为在计算二进制表示中1的数量的问题中，我认为相关数据的大小是数字表示的长度，而不是它的值，即比特流的长度。显然最坏情况是所有的1都需要N次迭代。

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

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

- Łukasz Zephyr

---

所讨论的代码使用小写字母n，并且由于该变量，复杂度被限制在O(log n)（小写字母）内。 - Antti Haapala -- Слава Україні

通常情况下，当算法处理整数时，变量N（大写）表示整数本身，而n（小写）表示位数，即n = log N。 - kaya3