Counting Bits

Q: Counting Bits 的时间复杂度是多少？

最佳答案的时间复杂度为 O(n)： n+1 个条目中的每一个，都由前面的一个条目加上一次加法得到。单独统计每个数字的位数需要 O(n log n) 时间。除输出数组外，两种方法都只使用 O(1) 的额外内存。

Q: 计算位数还有其他 O(n) 递推关系吗？

是的。 i & (i-1) 会清除 i 中最低位的 1，因此对于所有大于或等于 1 的 i ，都有 bits[i] = bits[i & (i-1)] + 1 。对于 12（ 1100 ）， 12 & 11 是 8（ 1000 ），其中有一个 1，所以 12 中有两个 1。

Q: 我可以使用内置的 popcount 函数吗？

对每个数字都调用一个函数，例如 Java 中的 Integer.bitCount 或 C 和 C++ 中的 __builtin_popcount ，可以得到正确答案。面试官通常会要求你实现不使用它的版本，因为这道题的重点是重复利用已经计算出的答案。

简单位运算动态规划

+10

给定一个大于或等于 0 的整数 n，返回一个包含 n+1 个元素的数组，其中对于从 0 到 n 的每个 i，元素 i 的值是 i 的二进制形式中 1 的个数。

函数

countBits(n: integer) → integer-array

ninteger: 要计数的最后一个数字，0 或更大
返回值integer-array: 一个包含 n+1 个计数值的数组，其中第 i 项是 i 中 1 位的数量

约束条件

0 ≤ n ≤ 2 × 10⁴

示例

输入: n = 2
输出: [0, 1, 1]
解释: 在二进制中，0 是 0，1 是 1，2 是 10：没有 1，然后有一个，再然后有一个。

输入: n = 5
输出: [0, 1, 1, 2, 1, 2]
解释: 3 是 11，5 是 101，两者都各有两个 1；4 是 100，有一个 1。加上第一个示例中的 0、1 和 2，计数依次为 0、1、1、2、1、2。

进阶

你能否在 O(n) 时间内填充整个数组，不使用内置的位计数函数，也不从头开始统计每个数字的位数？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

从头开始计算每个数字会重复做很多工作：13 是 1101，也就是 6 的二进制位（110）末尾再加一位。按递增顺序填写答案，每一项都能通过一次加法复用一个更小的结果。

统计每个数字的位数

思路

直接统计每个数字中值为 1 的位：将 x & 1 加到计数器中，把 x 右移一位，然后在它变为 0 时停止。对于 13（1101），各位依次为 1、0、1、1，所以计数为 3。

不超过 n 的数字约有 log2 n 个二进制位，因此运行时间为 O(n log n)：当 n = 2 × 10^4 时，大约需要 20,000 × 15 = 300,000 步。

算法

先创建一个空的结果列表。
对于从 0 到 n 的每个 i，将 count 设为 0，并将 x 设为 i。
当 x 大于 0 时，将 x & 1 加到 count 上，并将 x 右移一位。
将 count 添加到结果中。
返回结果。

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

构建在数字的一半上

思路

将 i 右移一位会删除它最后一个二进制位，而 i & 1 就是这个位。因此，i 中 1 的个数等于 i >> 1 中 1 的个数加上它最后一位的值：bits[i] = bits[i >> 1] + (i & 1)。

对于每个大于或等于 1 的 i，i >> 1 都小于 i，所以从左到右填充数组，并从 bits[0] = 0 开始，意味着你读取的值总是已经就绪。对于 n = 5：bits[3] = bits[1] + 1 = 2，bits[4] = bits[2] + 0 = 1，bits[5] = bits[2] + 1 = 2。

每个条目都需要一次移位、一次 AND 运算和一次加法：时间复杂度为 O(n)，除输出外不需要额外内存。

算法

创建一个由 n+1 个 0 组成的数组 bits。bits[0] 保持为 0。
对于从 1 到 n 的 i，将 bits[i] 设为 bits[i >> 1] + (i & 1)。
返回 bits。

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

易错点和边界情况

返回了 n 个条目，而不是 n+1 个。当 n = 0 时，答案是 [0]。
运算符优先级。在 Python、C、Java 和 JavaScript 中，+ 的优先级高于 &，因此 bits[i >> 1] + i & 1 表示 (bits[i >> 1] + i) & 1。要保留 (i & 1) 两边的括号。
查找的是 bits[i-1]，而不是 bits[i >> 1]。相邻数字之间没有简单的规律：7 的二进制表示是 111，有 3 个 1；8 的二进制表示是 1000，只有 1 个 1。
在 Lua 和 R 中，数组从 1 开始计数，因此 i 的计数位于索引 i+1 处，而对 i >> 1 的查找位于索引 floor(i/2) + 1 处。Lua 5.1 没有移位运算符，因此要用 math.floor(i / 2) 除以 2 并向下取整。

常见问题3

Counting Bits 的时间复杂度是多少？

最佳答案的时间复杂度为 O(n)：n+1 个条目中的每一个，都由前面的一个条目加上一次加法得到。单独统计每个数字的位数需要 O(n log n) 时间。除输出数组外，两种方法都只使用 O(1) 的额外内存。

计算位数还有其他 O(n) 递推关系吗？

是的。i & (i-1)会清除i中最低位的 1，因此对于所有大于或等于 1 的i，都有bits[i] = bits[i & (i-1)] + 1。对于 12（1100），12 & 11是 8（1000），其中有一个 1，所以 12 中有两个 1。

我可以使用内置的 popcount 函数吗？

对每个数字都调用一个函数，例如 Java 中的 Integer.bitCount 或 C 和 C++ 中的 __builtin_popcount，可以得到正确答案。面试官通常会要求你实现不使用它的版本，因为这道题的重点是重复利用已经计算出的答案。

def countBits(n):
    # 在这里编写代码

测试 #1

测试 #2

参数

n = 2

预期输出

[0, 1, 1]