位运算

---

题目详情

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

---

示例1：

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

示例2:

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

思路:
本题利用动态规划+位运算求解
dp[i]表示数字i的二进制含有1的数量
对于0~n这些连续的数字,它们的二进制表示的是…0 …1 …0 …1 末位是01交替的
对于i这个数字,如果它二进制的末位是1,那么说明i-1这个数字比i少一个1
所以dp[i] = dp[i-1] + 1
如果i这个数字末位是0,说明它末位进位了,i-1末位是1
但是我们还不知道前面的情况,比如3和4
0011 0100这种情况i反倒比i-1少一个1,那么我们不能简单地利用
i和i-1之间的关系判断,我们对于这种情况可以利用算术右移
i>>1一定比i小,所以dp[i>>1]一定已经计算过了,所以可以利用它来更新dp
所以本题的关键就是找到比i更小的一个值,来更新dp[i]
所以我们也可以利用i&(i-1)这个更小的值来更新

我的代码：

class Solution 
{
public:
    vector<int> countBits(int n) 
    {
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; ++i)
        {
        //i&1判断末位是否为1,如果是就↓,如果不是就和dp[i>>1]数量一样            
            dp[i] = i & 1? dp[i-1] + 1 : dp[i>>1];
            //等价于dp[i] = dp[i&(i-1)] + 1;
            /*在这个式子里,i&(i-1)将i中最低位的1给去除了
            不管去除的是末位还是更高位的1,这个值都比i小(dp存在)
            我们再把去除的1加回来即可
            */
        }
        return dp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

位运算常用技巧