Alice...【LeetCode】338. Counting Bits
目录
位运算
对于[0,n]的每个数字x，我们使用位运算对其进行二进制下1的个数的计算。
计算某个数字x二进制下1的个数count有以下方法：
1.用x和1进行与运算，当结果为1时代表当前位是1，则将count+1，每进行一次，将x右移一位。
int temp = x, count = 0;
while (temp) {
if (temp & 1 == 1) {
count += 1;
}
temp = temp >> 1;
}
2.用x和x-1进行与运算，每进行一次运算便将count+1。(x-1会将x最低位的1变为0，最低位的1右侧若有0，这些0会全部被置为1。当执行x=x&x-1时，会将x最低位的1置0，其他位不变。)
int temp = x, count = 0;
while (temp) {
count += 1;
temp = temp & (temp - 1);
}
计数时，第二种方法相对较快。本题使用第二种计数方法进行解答：
// 位运算
vector<int> countBits1(int num) {
vector<int> ans;
for (int i = 0; i <= num; i++) {
int temp = i, count = 0;
while (temp) {
count++;
temp &= temp - 1;
}
ans.push_back(count);
}
return ans;
}
动态规划
动态规划的核心就是建立递推关系。使用一个好的递推关系，就像是面对搭好的一排多米诺骨牌，最后用一点力，就能将它们从前往后轻松推倒。
本题中，使用动态规划的关键在于：找到当前的数x和比某个它小的数，在二进制下1的数目上存在的推导关系。
动态规划（从最高有效位入手）
对于某个数x，假设其最高的有效位为n，则存在以下递推关系：
x = bitcount[x-2^n] + 1
x-2^n的结果等于将x的最高有效位置0后得到的数字，该数字一定小于x且大于等于0。
bitcount数组中存放的是已求得的数字的二进制下的1计数，由于是从0到n依次求解，因此可以保证求解到x时，索引更小的bitcount[x-2^n]一定存在。
根据以上递推关系，可以稍作加工得到解答：
// 动态规划（最高有效位）
vector<int> countBits2(int num) {
vector<int> ans = {0};
int high_bit = 0; // 记录只有当前最高有效位为1的数字(上文中的2^n)
for (int i = 1; i <= num; i++) {
// 当i只有最高有效位时，更新high_bit
if ((i & i - 1) == 0) {
high_bit = i;
}
// 递推求解
ans.push_back(ans[i - high_bit] + 1);
}
return ans;
}
动态规划（从最低有效位入手）
对于某个数x，若将其右移一位，去除其最低有效位，得到的数大小为x//2，同时，存在以下递推关系：
若x为奇数（右移导致去除了一个1）：x = bitcount[x>>1] + 1
若x为偶数（右移导致去除了一个0）：x = bitcount[x>>1]
基于以上思路，可以解答：
//动态规划（最低有效位）
vector<int> countBits3(int num) {
vector<int> ans = {0};
for (int i = 1; i <= num; i++) {
if (i % 2 == 1) {
ans.push_back(ans[i >> 1] + 1);
} else {
ans.push_back(ans[i >> 1]);
}
}
return ans;
}