```
class Solution {
/// An easy recurrence for this problem is f[i] = f[i / 2] + i % 2.
func countBits(_ num: Int) -> [Int] {
if num < 0 {
return []
}
var dp = [Int](repeatElement(0, count: num + 1))
for i in 0...num {
dp[i] = dp[i >> 1] + (i & 1)
}
return dp
}
func countBits2(_ num: Int) -> [Int] {
if num < 0 {
return []
}
if num == 0 {
return [0]
}
var dp = [Int](repeatElement(0, count: num + 1))
for i in 1...num {
dp[i] = dp[i & (i - 1)] + 1
}
return dp
}
}
```