给定一个非负整数 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）来执行此操作。
**难度**: Medium
**标签**: 位运算、 动态规划、
# -*- coding: utf-8 -*-
# @Author : LG
"""
执行用时：88 ms, 在所有 Python3 提交中击败了92.93% 的用户
内存消耗：20.6 MB, 在所有 Python3 提交中击败了23.45% 的用户
解题思路：
某一数值num的比特位为1的计数，等于其 /2的余数为1 的数量
例：
13 余 6 余
/2 6 1 /2 3 0
/2 3 0 /2 1 1
/2 1 1 /2 0 1
/2 0 1
"""
class Solution:
def countBits(self, num: int) -> List[int]:
dp = [0 for _ in range(num+1)]
for i in range(1, num+1):
dp[i] = dp[i // 2] if i%2 == 0 else dp[i // 2]+1
return dp