题目：
给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。
示例 1:
输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。
说明: 1 <= n <= 10^9
思路：（动态规划）
设一个数组：用f(i)表示为长度为i不含连续1的二进制数（范围i个0~~i个1）的个数（类似于斐波那契数列）
可以观察得出：
| n=1 | n=2 | n=3 | n=4 | ||
|---|---|---|---|---|---|
| 0 | 00 | 000 | 0000 | 1000 | |
| 1 | 01 | 001 | 0001 | 1001 | |
| 10 | 010 | 0010 | 1010 | ||
| 11 | 011 | 0011 | 1011 | ||
| 100 | 0100 | 1100 | |||
| 101 | 0101 | 1101 | |||
| 110 | 0110 | 1110 | |||
| 111 | 0111 | 1111 | |||
| 2 | 3 | 5 | 8 | ||
f(i) =f(i-1)+f(i-2) 当n=0时，设为1，即f（0）=1；
要查找到所有满足条件的数（即不重，不漏），可以就是将给定范围内的数分几个阶段，看各个阶段满足条件的数。
开始将一个数转换为二进制，从最高有效位（左->右）扫描，每当遇见一个1即（1*****，1后面有k个二进制位，每个*可以为1或0），满足不含有连续1的二进制数的总个数count 就需要增加f(k)，因为我们可以在这个数字上放一个'0'，后面放任意一个有效长度为k的字符串；之后，我们继续循环考虑剩下的情况，也就是说，我们在这个digit上放一个'1'。如果发现有连续的1，我们就退出循环并返回答案。在循环结束时，我们返回count+1，包括数字n本身。
例如，如果n是10010110，接下来需要找到比n小的且没有连续1的数:
1.我们只把第1个有效位1换为0，这个1后面怎么放数字，都会比n小，其中最大的数是末尾7位都是“1”的数，这些数可以用范围 00000000-01111111表示，其中满足不含有连续1的二进制数的个数为 f(7)。
2.我们只把第2个有效位1换为0，这个1后面怎么放数字，都会比n小，其中最大的数是末尾4位都是“1”的数，这些数可以用范围 10000000-10001111表示，数的个数为 0000-1111，其中满足不含有连续1的二进制数的个数为f(4)。
3.我们只把第3个有效位1换为0，这个1后面怎么放数字，都会比n小，其中最大的数是末尾2位都是“1”的数，这些数可以用范围10010000-10010011表示，数的个数为 00~11，其中满足不含有连续1的二进制数的个数为f(2)。
4.我们只把第4个有效位1换为0，这个1后面怎么放数字，都会比n小，其中最大的数是末尾1位是“1”的数，些数可以用范围 10010100-10010101表示，数的个数为 0~1，其中满足不含有连续1的二进制数的个数为f(1)。
注: 数的二进制表示中有几个1(比如，有k个1)，这里就有几个(k个)步骤。
接下来的操作是需要在二进制数 1001011x 上做变换的，但1001011x已出现连续的1，非法了，故不进入计数。
图示：
代码：
（这里是将二进制数字转换成了字符串，并且用了32长度的字符串存斐波那契数列的各个值，内存消耗过大）
class Solution {
public:
//函数将一个数转换为二进制字符串
string binaryStr(int num) {
//定义一个字符串来接受转换而来的二进制字符串
string st = "";
while (num>0)
{
//将求出的数转换为对应字符'0'或'1'
char c = num % 2 + '0';
st.push_back(c);//这里是二进制低位在前高位在后
num /= 2;
}
//反转，因为我们要的是高位在前低位在后
reverse(st.begin(), st.end());
return st;
}
//最后要返回
int num=0;
int findIntegers(int n) {
//初始化斐波那契数列
//int 32位
vector<int> f(32);
f[0] = 1;
f[1] = 2;
for (int i = 2; i < 32; i++) {
f[i] = f[i - 1] + f[i - 2];
}
string str1 = binaryStr(n);
for (int i = 0; i < str1.size(); i++) {
if (str1[i] == '0') continue;
num += f[str1.size() - 1 - i];
if (i != 0 && str1[i - 1] == '1') return num;
}
//加1代表n本身也是一个
return num + 1;
}
};
第二版:写一个函数用来求斐波那契数列的各个值，用变量k表示有效数字1后面的二进制位数
class Solution {
public:
//求斐波那契数列函数
int feiB(int num) {
int f_1 = 1, f_2 = 2, f_3 = 3;
if (num == 0) return f_1;
if (num == 1)return f_2;
for (int i = 2; i <= num; i++){
f_3 = f_1 + f_2;
f_1 = f_2;
f_2 = f_3;
}
return f_3;
}
int findIntegers(int n) {
//最后要返回
int num = 0;
//记录前一位数字，因为前连续两位位1，后面不用看了
int preBit = 0;
//int型数据最大为2^31-1,31位最多有数字，取不到32位
int k = 30;
while (k>=0)
{
//1左移30位，即1后面30个0
//判断k位是否为1
if (n & (1 << k)) {
//cout << k<<endl;;
num += feiB(k);
if (preBit) return num;
preBit = 1;
}
else
{
preBit = 0;
}
k--;
}
return num + 1;
}
};