难度: Easy
给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
示例 1:
输入: n = 2 输出: [0,1,1] 解释: 0 --> 0 1 --> 1 2 --> 10
示例 2:
输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
说明 :
0 <= n <= 105进阶:
O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？O(n) 。__builtin_popcount ）来执行此操作。注意：本题与主站 338 题相同：https://leetcode-cn.com/problems/counting-bits/
运行时间: 26 ms
内存: 16.8 MB
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i & (i - 1)] + 1
return ans
这个题解使用了动态规划的思想，依据已知的较小数字的比特位计数来确定更大数字的比特位计数。核心在于利用位运算的性质：对于任何整数i，i & (i - 1)的运算结果是将i的二进制表示中最低位的1变为0。因此，i中1的个数等于i & (i - 1)中1的个数加1。这样，通过从1遍历到n，我们可以逐个计算出每个数字的比特位1的数量。
时间复杂度: O(n)
空间复杂度: O(n)
# 定义解决方案类
class Solution:
# 定义计算从0到n每个数字比特位1的数量的函数
def countBits(self, n: int) -> List[int]:
# 初始化结果列表，长度为n+1，所有元素初值设为0
ans = [0] * (n + 1)
# 从1遍历到n
for i in range(1, n + 1):
# 动态规划关系：当前数字i的1的个数等于去掉最低位1后的数字的1的个数加1
ans[i] = ans[i & (i - 1)] + 1
# 返回结果列表
return ans
这个动态规划关系基于一个重要的位运算性质：对于任何整数i，表达式`i & (i - 1)`的结果是将i的最低位的1变为0。如果我们知道一个数比如`i & (i - 1)`的1的个数，那么i的1的个数就是`i & (i - 1)`的1的个数加上那个被移除的最低位1。换句话说，每当我们在i的二进制表示中去掉最低位的1，我们就知道新数的比特位计数比原数少一个1。因此，通过已知的更小的数的计数，我们可以构建出更大的数的比特位计数，这确保了计算的准确性。
是的，题解中的算法考虑了所有可能的输入情况，包括最小的输入情况n=0。在算法中，初始化的结果列表`ans`的长度为`n+1`，并且所有元素的初值设为0。当n=0时，列表长度为1，且唯一的元素ans[0]已经正确设置为0，这代表数字0的二进制中1的个数是0。因此，算法对于输入n=0也提供了正确的输出。
位运算`i & (i - 1)`的工作原理是：当我们计算`i & (i - 1)`时，从i的二进制表示中去除最低位的1。例如，如果i=14（二进制1110），则`i - 1`为13（二进制1101），而`i & (i - 1)`为12（二进制1100），即最低位的1被去除。这个操作有助于减少计算量，因为它允许我们利用已经计算过的结果（即`i & (i - 1)`的比特位计数）来计算当前i的比特位计数。这样，每个数的计数只需要常数时间O(1)，从而使整个算法时间复杂度为O(n)。