# Counting bits

medium | Accept. 79% | 力扣中文站

Given a non-negative integer number **num**.
For every number **i** in the range **0 ≤ i ≤ num**
calculate the number of 1’s in their binary representation and return them as an array.

**Example 1:**

```
Input: 2
Output: [0,1,1]
```

**Example 2:**

```
Input: 5
Output: [0,1,1,2,1,2]
```

## Code

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

## Intuition

How do we get the result at `dp[i]`

based on previous results?

There are two cases:

- When the number
`i`

is even, the least significant bit is`0`

. If we right shift`i`

by`1`

, we effectively drop the trailing`0`

, and the set bit count remains the same. - When the number
`i`

is odd, compare it with the previous number, which is even. Numerically,`i`

is 1 greater than`i - 1`

, and the set bit count is also 1 greater.

```
0 | 0000 0000
1 | 0000 0001
2 | 0000 0010
3 | 0000 0011
4 | 0000 0100
5 | 0000 0101
```

## Reference

How we handle this question on interview [Thinking process + DP solution] - LeetCode Discuss