338. 比特位计数

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

思路1：
首先这个题目要计算的是每一个数字上的比特位1的个数并在数组中保存，比较直接的计算方法是对输入的数字N进行遍历，并且遍历每一个数字，右移一位与1进行与操作，

vector ret(num+1);
for(int i = 0;i<=n;i++)
	if(i ==0||i==1)
		{
			ret[i] = i;
		}
		else{
			count = 0;
			for(int j = 0;j<=32;j++){
				if((i>>j)&1!=0)
				{
					continue;
				}else{
					count++;
					}
			}
			ret[i] = count;
		}

但是这样的遍历方法,效率极低，所以采用第二种方法，采用数学归纳的方法并且附带动态规划的方法
如果i为从偶数变为奇数：则在偶数的前提下+1
0 = 0 1 = 1
2 = 10 3 = 11
如果当前i为偶数，则证明下一个偶数是在当前偶数的基础上左移一位计算，末尾为0，所以1的个数没有变化。
2 = 10 4 = 100 8 = 1000
3 = 11 6 = 110 12 = 1100
所以在计算的时候只需要计算0，1，2即可，其中0中的1为0，1中的1个数为0+1；而2中的1的个数为1；其他的各个数字均可以在这个基础上进行演变

class Solution {
public:
    vector countBits(int n) {
        vector ret_vec(n+1);
        ret_vec[0] = 0;        
        for(int i = 1;i<=n;i++){
            if(i & 1 !=0)//奇数
            {
                ret_vec[i] = ret_vec[i-1]+1;
            }else
            {
                ret_vec[i] = ret_vec[i/2];
            }
        }
        return ret_vec;

    }
};