Consider for num > 0:

- If num is even: countBits(num) = countBits(num/2).
- If num is odd: countBits(num) = countBits(num/2) + 1.
- In other words: countBits(num) = countBits(num >> 1) + (num & 1).

Of course, implementing this with recursion would lead to a terrible runtime. Instead do it bottom up (that is, dynamic programming).

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