338. 比特位计数

题目链接：https://leetcode.cn/problems/counting-bits/
难度：简单

描述：
给你一个整数 n ，对于0 <= i <= n中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

题解

class Solution:
    def countBits(self, n: int) -> List[int]:
        r = [0] * (n+1)
        for i in range(1, n+1):
            # n & n-1 会消去n的最低位的1
            r[i] = r[i & (i-1)] + 1
        return r