# \[338]\[中等]\[动态规划] 比特位计数

## 题目描述

[338. 比特位计数](https://leetcode-cn.com/problems/counting-bits/)

给定一个非负整数 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）来执行此操作。

## 解题思路

在时间复杂度要求是$$O(n)$$的情况下, 就不能遍历每个数字数1了, 需要结合之前遍历数字的结果信息, 减少重复的计算, 因此需要使用动态规划的方法

### 奇偶数规律

参考: [清晰的思路](https://leetcode-cn.com/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/)

对于所有的数字, 只有两类:

* 奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1
* 偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的

初始条件为数字0中为1位的个数是0.

```python
class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        for i in range(1, num + 1):
            if i & 1 == 0:
                bits.append(bits[i // 2])
            else:
                bits.append(bits[i - 1] + 1)
        return bits
```

### 最高有效位

计算数字$$i$$的**一比特数**时, 其二进制表达的最高为值肯定为1, 而使用从小到大遍历的方法, 抛开这个最高位的1, 剩余的位数组成的数字, 之前肯定见过, 也记录过这个数字的比特数.

因此当前数$$i$$的一比特数就是其最高位对应的数字, 设为$$j$$, 以及剩余部分$$z=i-j$$对应的比特数, 而这个数字在动态规划遍历的过程中已经记录了.

所以我们要使用一个变量记录当前的最高位. 最高位数字有个特点, 它只有最高位位1, 其余位都是0, 因此使用$$y&(y-1)==0$$来判断当前数字是否是最高位, 因为$$y&(y-1)==0$$的作用是将$$y$$中最低的1位置0.

或者满足最高位的数字肯定是2的整数次幂, 可以利用这个方法记录当前的最大的2的整数次幂.

```python
class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        highBit = 0
        for i in range(1, num + 1):
            if i & (i - 1) == 0:
                highBit = i
            bits.append(bits[i - highBit] + 1)
        return bits
```

或者省略记录, 直接寻找去掉最高位后剩余位数组成数字中的一比特数, 然后直接加一即可.

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

## 参考资料

* [清晰的思路](https://leetcode-cn.com/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/)
* [比特位计数](https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/338-bi-te-wei-ji-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.