LeetCode位计数，中等难度，记录下解题思路
输入一个数num，需要求[0,num]区间内所有数对应的二进制数中1的数量
计算一个数的二进制中1的个数，可以直接将一个数转换为二进制例如5 = 2^2 + 2^0 = 101
也可以拆分为5 = 4 + 1
其中4直接是2^2对应的就是100，是除了第一位以外所有的数均为0的情况，之后加上2^0即001，那么就可以得到101
那么运用动态规划的思路：
1 = 2^0
2 = 2^1
3 = 2^1 + 2^0
4 = 2^2
5 = 2^2 + 2^0
6 = 2^2 + 2^1
7 =2^2 + 2^1 + 2^0
如果一个数是2的整次幂，那么这个数二进制对应1的个数为1
如果一个数不是2的整次幂，那么这个数可以拆分为res[i] = res[i -最近一个整数次幂的数] + 1，res数组是对应数字二进制中1的个数
例如：
res[5] = res[5-4] + 1 = 2
res[6] = res[6-4] + 1 = res[2] + 1 = 2
res[7] = res[7-4] + 1 = res[3] + 1 = res[3-2] + 1 + 1 = res[1] + 1 + 1 = 3
这样推导下来就能很清楚的看到动态规划的公式，所以最后实现的过程如下：
- 遍历[0,num]中间所有数，并且已知
res[0] = 0 - 如果这个数是2的整数次幂就保存下来，记为
high，并且这个数的count = 1
判断整数次幂用i & (i - 1)) === 0
例如4 = 100和3 = 011来做与运算结果就是0
5 = 101和4 = 100做与运算结果为100不为0 - 如果这个数不是2的整数次幂，就查用保存的
high和当前数相减res[i] = res[i - high] + 1这个公式来计算结果
var countBits = function(num) {
// 创建结果数组
const res= new Array(num + 1).fill(0);
// 定义当前最高位为0
let highBit = 0;
// 从1开始遍历整个数
for (let i = 1; i <= num; i++) {
// 如果是2的整数次幂
if ((i & (i - 1)) === 0) {
// 保存当前数
high = i;
// 将当前数对应的结果设为1
res[i] = 1
// 跳出本次循环
continue
}
// 计算结果
res[i] = res[i - high] + 1;
}
return res;
}
