# 338. Counting Bits

[Link](https://leetcode.com/problems/counting-bits/)

**Solution**

觀察 i跟 dp\[i]的關係

2   010 \
​3   **011**\
4   100 \
5   101\
6   **110**\
7   111\
若i的lastbit bit為0 則 dp\[i] == dp\[i >> 1] ( ex. dp\[6]  == dp\[3])\
反之若lastbit為 1， 則 dp\[i] == dp\[i>>1] + 1 (ex. dp\[5] == dp\[2] + 1)

dp\[i] = dp\[i >> 1] + (i&1);

```
 public int[] countBits(int num) {
        int[] dp = new int[num+1];
        dp[0] = 0;
        for(int i = 1; i <= num; i++){
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
```

\\
