题目连接
https://leetcode-cn.com/problems/counting-bits/
解题思路
这道题需要计算从 0 到 num 的每个数的二进制表示中的 1 的数目。最直观的方法是对每个数直接计算二进制表示中的 1 的数目，时间复杂度较高。也可以使用动态规划的方法，时间复杂度较低。
为了表述简洁，下文用「一比特数」表示二进制表示中的 1 的数目。
方法一：暴力
暴力，时间复杂度O(n*sizeof(integer))
注意，虽然是暴力，但是仍可以进行优化。
按位与运算（&）的一个性质是：
对于任意整数 x，令 x=x&(x−1)，该运算将 x 的二进制表示的最后一个 1变成 0。
因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」
方法二：dp
-
最高有效位
方法一需要对每个数遍历其二进制表示的每一位。可以换一个思路，当计算 i 的「一比特数」时，如果存在 0≤j<i，j 的「一比特数」已知，且 i 和 j 相比，i 的二进制表示只多了一个 1，则可以快速得到 i 的「一比特数」。
令 bits[i] 表示 i 的「一比特数」，则上述关系可以表示成：bits[i] = bits[j]+1。
对于正整数 x，如果可以知道最大的正整数 y，使得 y≤x 且 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，此时称 y 为 x 的「最高有效位」。令 z=x-y，显然 0≤z<x，则 bits[x] = bits[z]+1。
为了判断一个正整数是不是 2 的整数次幂，可以利用方法一中提到的按位与运算的性质。如果正整数 y 是 2 的整数次幂，则 y 的二进制表示中只有最高位是 1，其余都是 0，因此 y&(y−1)=0。由此可见，正整数 y 是 2 的整数次幂，当且仅当 y&(y−1)=0。
显然，0 的「一比特数」为 0。使用 highBit 表示当前的最高有效位，遍历从 1 到 num 的每个正整数 i，进行如下操作。
如果 i&(i−1)=0，则令 highBit=i，更新当前的最高有效位。
i 比 i−highBit 的「一比特数」多 1，由于是从小到大遍历每个数，因此遍历到 i 时，i−highBit 的「一比特数」已知，令 bits[i]=bits[i−highBit]+1。
最终得到的数组 bits 即为答案。
class Solution {
public:
vector<int> countBits(int num) {
int highBit = 0;
vector<int> ans;
ans.push_back(0);
for(int i = 1;i <= num ; i++){
if((i & (i - 1)) == 0) highBit = i;
ans.push_back(ans[i - highBit] + 1);
}
return ans;
}
};
class Solution {
public int[] countBits(int num) {
int[] ans = new int[num+1]; // 初始化为0，声明不会初始化，但是new之后会初始化
int highBit = 0;
for(int i = 1;i <= num; i++){
if((i & (i-1)) == 0) highBit = i;
ans[i] = ans[i - highBit] + 1;
}
return ans;
}
}
-
最低有效位
方法二需要实时维护最高有效位，当遍历到的数是 2 的整数次幂时，需要更新最高有效位。如果再换一个思路，可以使用「最低有效位」计算「一比特数」。
对于正整数 x，将其二进制表示右移一位，等价于将其二进制表示的最低位去掉，得到的数是 ⌊ x/2 ⌋。如果 bits[⌊ x/2 ⌋] 的值已知，则可以得到 bits[x] 的值：
如果 x 是偶数，则 bits[x]=bits[⌊ x/2 ⌋]；
如果 x 是奇数，则 bits[x]=bits[⌊ x/2 ⌋]+1。
上述两种情况可以合并成：bits[x] 的值等于 bits[⌊ x/2 ⌋] 的值加上 x 除以 2 的余数。
由于 ⌊ x/2 ⌋ 可以通过 x>>1 得到，x 除以 2 的余数可以通过 x&1 得到，因此有bits[x]=bits[x>>1]+(x&1)。
遍历从 1 到 num 的每个正整数 i，计算 bits 的值。最终得到的数组 bits 即为答案。
class Solution {
public int[] countBits(int num) {
int[] ans = new int[num+1];
int highBit = 0;
for(int i = 1;i <= num; i++){
ans[i] = ans[i >> 1] + (i & 1);
}
return ans;
}
}
-
最低设置位
定义正整数 xx 的「最低设置位」为 xx 的二进制表示中的最低的 11 所在位。例如，1010 的二进制表示是 1010 ，其最低设置位为 2，对应的二进制表示是 10 。
令 y=x&(x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然 0≤y<x，bits[x]=bits[y]+1。因此对任意正整数 x，都有 bits[x]=bits[x&(x−1)]+1。
遍历从 1 到 num 的每个正整数 i，计算 bits 的值。最终得到的数组 bits 即为答案。
class Solution {
public int[] countBits(int num) {
int[] ans = new int[num+1];
int highBit = 0;
for(int i = 1;i <= num; i++){
ans[i] = ans[(i & (i-1))] + 1;
}
return ans;
}
}
总结
类似于找规律，但是将找规律的本质提炼出来就是dp的转移方程。
前置知识：x=x&(x-1)可以使x的最后一个1变为0
推论：若x&(x-1)=0则说明x为2的正整数次幂
巧用dp思想：bits[i] = bits[j]+1
举一反三：i比j多的哪一位的1，可以是最高位的1，最低位的1，或者是最低位（若odd，若even）
