题目
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
题意
给定一个数字num,求0<=i<=num中每个数二进制中1的个数。返回一个数组
例子
Input: 5
Output: [0,1,1,2,1,2]
题解
若i为偶数，则1的个数等于i/2的1的个数，若为奇数，则为i/2的1的个数+1;因为对于偶数，除与2就是右移一位，所以1的个数是相同的。对于奇数，除以2也是右移一位，只是最后一位1被去掉了，所以要补回来。
代码
func countBits(num int) []int {
res := make([]int,num+1,num+1)
for i:=0;i<=num;i++{
res[i] = res[i>>1] + i&1
}
return res
}
总结
需要找到规律，其实发现之后这道题也变得十分简单。
