**Solution**

**Counting Bits** https://leetcode.com/problems/counting-bits/

**Algorithm: n&(n-1) trick**

- First algorithm is to use the trick n & (n-1) which resets the lowest set bit to 0. Use this to count the number of set bits in each input number.

```
class Solution(object):
def count_ones(self, n):
cnt = 0
while n:
n = n & (n-1)
cnt += 1
return cnt
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
result = []
for i in range(num+1):
result.append(self.count_ones(i))
return result
```

**Dynamic programming**

- Use the recursive idea in counting the number of set bits. The idea if to test the last bit if it is 0 or 1 and look up the number of bits in n >> 1 or n/2. https://discuss.leetcode.com/topic/40162/three-line-java-solution

```
class Solution(object):
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
result = [0]
for i in range(1, num+1):
result.append(result[i>>1] + int(i&1))
return result
```