本文共 595 字，大约阅读时间需要 1 分钟。

这题的特殊之处在于采用了二进制位的递推方法，而不是传统的动态规划（dp）方式。这种方法通过对二进制位进行递推来计算数位的数量。

递推方法解释

举个例子来理解这一点可能会更清楚：比如，数字11001可以分解为1100 + 1&1。这里的1&1实际上是对最低有效位进行操作，相当于将最低有效位单独提取出来。

代码解析

以下是实现这一递推方法的C++代码：

class Solution {
public:
    vector
   
     countBits(int num) {
        vector
    
      dp(num + 1);
        for (int i = 1; i <= num; ++i) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
};
    
   

递推逻辑

• dp[i] = dp[i >> 1] + (i & 1)
• 这里的dp[i >> 1]表示将i右移一位后的结果，相当于去掉了最低有效位。
• (i & 1)则是提取出i的最低有效位，值为0或1。
• 因此，dp[i]实际上是i的二进制位数，比如i=3(二进制为11)，dp[3]=dp[1]+1=3。

这种递推方法通过逐位处理数字，避免了传统dp的复杂性，简化了数位计算过程。

转载地址：http://scqv.baihongyu.com/