如何在O(n)时间内计算0、1、2、...、n中设置的1位数的数量？

Question

这是一道面试题。原问题如下：

给定一个正整数N，计算从0到N中每个整数的1的数量，并将计数返回大小为N + 1的数组中。在O(n)时间内完成。

例如：

给定7，返回[0、1、1、2、1、2、2、3]。

当然，最简单的方法是创建一个循环来计算每个整数的1的数量，但这将需要O(kn)的时间，其中k是整数位数的大小。因此，要么有一种方法可以在O(1)的时间内计算整数的1的数量，要么有一种方法可以直接生成从0到N的计数。我相信两种方法都存在，但我想不出任何一种。

- bli00

---

@Idos，我认为这个问题与链接答案中描述的问题有足够的不同，因此不会被视为重复。 - templatetypedef

Answer 1

以下是一个简单易懂的方法，可以在O(n)时间内解决问题。假设你想知道数字k中有多少个二进制位为1，同时你已经知道数字0到k-1中有多少个二进制位为1。如果你能找到一种方法来清除数字k中任何一个二进制位为1，你就可以得到一个更小的数字（我们称之为m），而k中的二进制位数就等于m中的二进制位数再加上1。因此，只要我们能找到一种方法来清除数字k中的任何一个二进制位为1，我们就可以使用这种模式来解决问题：

result[0] = 0  // No bits set in 0
for k = 1 to n:
    let m = k, with some 1 bit cleared
    result[k] = result[m] + 1

有一个著名的位操作技巧，其中

 k & (k - 1)

给定一个数字k，清除k中设置的最低位1，返回结果数字。假设机器可以以常数时间执行位运算（这通常是一个合理的假设），则此操作的时间复杂度为O(1)。下面的伪代码可以实现该功能：

result[0] = 0
for k = 1 to n:
    result[k] = result[k & (k - 1)] + 1

这个操作每个数字只需要 O(1) 的时间，总共需要执行 O(n) 次，因此总的时间复杂度为 O(n)。

以下是另一种方法。举个例子，假设你已经知道了 0、1、2 和 3 这几个数字中二进制位上出现的次数，那么你就可以利用这些信息来计算出 4、5、6 和 7 中二进制位上出现的次数，因为这些数字的二进制表示都是在 0、1、2 和 3 的二进制表示前面加上一个 1 得到的。同样地，如果你已经知道了 0 到 7 中每个数字二进制位上出现的次数，那么你也可以通过在每个较小的数字二进制表示前面添加一个 1 来计算出 8、9、10、11、12、13、14 和 15 中二进制位上出现的次数。下面是相应的伪代码，为了简化起见，假设 n 是形如 2^k - 1 的形式，但是它也很容易适应于一般的 n：

result[0] = 0;
for (int powerOfTwo = 1; powerOfTwo < n; powerOfTwo *= 2) {
    for (int i = 0; i < powerOfTwo; i++) {
        result[powerOfTwo + i] = result[i] + 1;
    }
}

这个算法的时间复杂度为O(n)。要看到这一点，注意在这里所有循环的所有迭代中，数组中的每个条目都只写入了一次，并且确定要放入该插槽的值需要进行O(1)的工作。

- templatetypedef

---

虽然这肯定是个不错的加速，但我不确定它真的改变了渐进复杂度。如果我们认为整数中的位数也是常数，那么 OP 的天真算法已经是 O(n)。如果我们不这样做（即位数是 O(log n)），那么这些算法将需要O(n log n)时间，再次与OP的天真算法相同。 - Henry

@Henry 如果我们假设一个双分模型，其中机器字的操作时间为O(1)，但是机器字中的位数被认为是O(log n)，那么这两种方法都将花费O(n)的时间（独立于位数），因为它们只使用字操作。使用朴素方法逐个计算位需要O(log n)个字操作，因此其运行时间为O(n log n)。这些方法在实践中也会更慢。 - templatetypedef

好棒的技巧！我注意到了2^k - 1的关系，一直在试图推导出类似这样的通用公式，但这个完美无缺！ - bli00

@henry：即使我们使用时间复杂度的位计数模型（在我看来很少有用），重复增加一个数字的摊销成本也是O(1)，因为一半的时间只检查一个位；四分之一的时间，它是两个位；八分之一的时间是三个位，等等。对于大多数序列的分布，类似的论证适用于将一个系列中的一个数加一。你可以说需要一个位拷贝，但即使如此，在位计数的大小中，位数是log log n，而不是log n。 - rici

毫无疑问，天真的方法要慢得多。问题在于时间复杂度。我同意你的分析，但是假设“按位与”或“加法”的O(1)，同时对于计算位数的O(log n)并不合适。 - Henry

@rici 是的，你是对的，如果我们把 k & (k-1) 视为一个单独的操作，在第一种方法（使用&）中也可以使用类似的论据。 - Henry

Answer 2

更简单的回答：

令x为长度为k+1的数组，x[i]表示i中置位的数量。

x[0] = 0
for i=1:k
    x[i] = x[i>>1] + i&1

- ElKamina

Answer 3

我们从手动计算一些小数字的比特数开始。我们注意到n的比特数与之前结果之间存在一种递归关系：

 n: | count(n): | recurrence:
==============================
  0 |        0 |
  1 |        1 |
------------------------------
 10 |        1 | =  count(0) + 1
 11 |        2 | =  count(1) + 1
------------------------------
100 |        1 | =  count(0) + 1
101 |        2 | =  count(1) + 1
110 |        2 | = count(10) + 1
111 |        3 | = count(11) + 1
...

在给定所有比特数的情况下，例如2 = 2¹，我们可以通过加1来计算出4 = 2²的比特数。在给定了4 = 2²的比特数的情况下，我们可以通过加1来计算出8 = 2³的比特数。我们将其推广到二的k次幂，并可以得出以下示例实现：

// Counts and returns number of enabled bits for integers 0 - n:
function count_bits(n) {
  let count = new Array(n);
  count[0] = 0;
  for (let i = 1, j = 0, k = 1; i <= n; ++i, ++j) {
    if (i == 2**k) { // k-th bit of i has been enabled
      k++;
      j = 0;
    }
    count[i] = count[j] + 1;
  }
  return count;
}

// Example:
console.log(count_bits(17).join());

我们注意到，所有涉及的操作都是通过加一、随机数组访问、复制数组元素以及检查循环增量 i 的第 k 位来完成的，可以通过 i == 2**k 来重写它，也可以通过 i & 1 << k 来重写它，或者对于任意精度的 i，可以通过随机数组访问来重写它。

假设我们机器上列出的所有原始操作都是 O(1) 的，那么总运行时复杂度为 O(n)。

这同样适用于任意精度整数——其中增量具有 平均 运行时复杂度为 O(1)，除非复制 count[i] = count[j] + 1 花费的时间超过常数时间。由于这恰恰是针对任意大的整数的情况，因此我们的运行时复杂度为 O(n log(log(n)))，因为我们需要 O(log(log(n))) 的空间来存储 n 的位计数。

- le_m

---

非常抱歉如果我错了，但是你在这里描述的算法不是我在答案中提出的第二个算法吗？ - templatetypedef

@templatetypedef 是的，它与此处描述的相同。 - le_m

@templatetypedef 顺便问一下，你同意对于任意大的输入使用O(n log(log(n)))吗？ - le_m