> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/counting-bits.md).

# Counting Bits

<https://leetcode.com/problems/counting-bits/description/>

> Given a non negative integer number**num**. For every numbers**i**in the range**0 ≤ i ≤ num**calculate the number of 1's in their binary representation and return them as an array.
>
> **Example:**\
> For`num = 5`you should return`[0,1,1,2,1,2]`.

## Thoughts

没有做出来。

看到别人的解法，把nums分成两组：最后一位和除最后一位的前面的所有位。最后一位是否为1判断很简单，把nums%2即可。那前面所有位等于什么呢，由于是二进制，刚好等于nums/2。

## Code

```
class Solution {
    public int[] countBits(int num) {
        int[] f = new int[num + 1];
        if (num == 0) {
            return f;
        }  
        f[0] = 0;
        f[1] = 1;
        if (num == 1) {
            return f;
        }
        for (int i = 2; i < num + 1; i++) {
            f[i] = f[i >> 1] + f[i % 2];
        }

        return f;
    }
}
```

## Analysis

时间复杂度O(n)