338-counting-bits.md

338. 比特位计数 - medium

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

示例 2:

输入: 5
输出: [0,1,1,2,1,2]

进阶:

• 给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
• 要求算法的空间复杂度为O(n)。
• 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

Solutions

1. 动态规划 + 最高有效位

当 i & (i - 1) == 0 时，说明 i 是 2 的 n 次方。此时 bits[i] = 1。记此时 i 为最高有效位 hb，有 bits[i] = bits[i - hb] + 1（i - hb 就是去掉最高位的 1）。

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0] * (num + 1)
        hb = 0
        for i in range(1, num + 1):
            if i & (i - 1) == 0:
                hb = i
                bits[i] = 1
            else:
                bits[i] = bits[i - hb] + 1
            
        return bits

时间复杂度 O(n)；空间复杂度 O(1)

2. 动态规划 + 最低有效位

将 i 右移一位，则有 �bits[i] = bits[i >> 1] + 1 当 i 是奇数; bits[i] = bits[i >> 1] 当 i 是偶数。i >> 1 = i/2, 一定有 i/2 < i 所以可以利用前面的计算结果。

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0] * (num + 1)
        for i in range(1, num + 1):
            bits[i] = bits[i >> 1] + (i & 1)
        return bits

时间负责度：O(n)；空间复杂度：O(1)

3. 动态规划 + 最低设置位

将 i 最后一位 1 变成 0 的运算为 i & (i - 1)，当 i > 0 时，有i & (i - 1) < i。那就有 bits[i] = bits[i & (i - 1)] + 1

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0] * (num + 1)
        for i in range(1, num + 1):
            bits[i] = bits[i & (i - 1)] + 1
        return bits