本题源自leetcode 600 https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/discuss/
=----------------------------------------------------------------------
思路: 动态规划 用斐波那契数列
代码:
int findIntegers(int num) { vector<int> dp(32,0); dp[0] = 1; dp[1] = 2; for(int i = 2; i < 32;i++){ dp[i] = dp[i - 1] + dp[i - 2]; } int res = 0; int pre_bit = 0; int k = 30; while(k >= 0){ if(num & (1 << k)){ res += dp[k]; if(pre_bit) return res; pre_bit = 1; } else pre_bit = 0; k--; } return res + 1; }