给定一个正整数N，求0~N之间满足其二进制表示不包含连续的1，求这样的数有多少个

/*
给定一个正整数n，
求出0到n中有几个数满足其二进制表示不包含连续的1。

输入描述:
输入一个整数N（1<=N<=10^9）

输出描述:
满足其二进制表示不包含连续的1的数的个数

输入例子1:
5

输出例子
5
*/
//用dp，使用斐波那契数列。
#include "stdafx.h"
#include<vector>
#include<string>
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int findIntegers(int num);
int main()
{
    cout << findIntegers(6144) << endl;
    system("pause");
    return 0;
}
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;
}