题目原址
https://leetcode.com/problems/counting-bits/description/
题目描述
给定一个整数n，返回从1到n对应的数字的二进制上的1的个数，将结果存在数组中返回。
数字二进制与前面数的关系二进制中1的个数
100011200101300112 + 12401001501014 + 12601104 + 22701114 + 33810001910018 + 121010108 + 221110118 + 331211008 + 421311018 + 531411108 + 631511118 + 74
可以看出，每到2的幂数的时候，1的个数就变位1，然后再依次增加1咯，直到到下一个幂数。
AC代码
class Solution {
public int[] countBits(
int num) {
int pow =
1;
int p =
1;
int[] ret =
new int[num +
1];
for(
int i =
1; i <= num; i++) {
if(
pow == i){
ret[i] =
1;
pow <<=
1;
p =
1;
}
else {
ret[i] = ret[p] +
1;
p ++;
}
}
return ret;
}
}
