Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT containconsecutive ones.

Example 1:

Input: 5
Output: 5
Explanation: 
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 

Note: 1 <= n <= 109

题目：

https://leetcode.com/contest/leetcode-weekly-contest-34/problems/non-negative-integers-without-consecutive-ones/

给定的数字num，转换成二进制，共n位。

首先由上一题的结论，得到f[i]，1 <= i < n

假设数字num为从高位到低位B： bn-1, bn-2, ..., 3,2,1

　　　应该在比num小或相等的数字中，计算没有连续二进制1的数字的个数。

　　　从高位到低位，遍历B，如果遇到1，则对应位改变为0后，则肯定比原num小。

　　　　　如:10110，从高到低遍历二进制位

　　　　   第一个1，前缀变为0，剩下四位，比原来的num小，则满足条件的数字个数为f(4)

　　　　　第二个1，前缀变为100，剩下两位，100XX，比原来的num小，则满足条件的数字个数为f(2)

　　　　   第三个1，前缀变为1010，剩下一位，1010X，比原来的num小，则满足条件的数字个数为f(1)

　　　　   遍历过程中，当遇到两个连续的1时需要中止遍历。如原num为1XX11XXX，继续遍历找到后面的1并改变为0，得到的数字确实比num小，但不满足不存在连续1的条件。

　　　　　遍历过程中，考虑的都是比原num小的数，最后还需要判断一下原num是否符合条件。

    int findIntegers(int num) {
        vector<int> b_num;
        //int tmp = num;
        while( num != 0 )
        {
            b_num.push_back( num % 2 );
            num /= 2;
        }
        int f[32] = { 0 };
        f[0] = 1;
        f[1] = 2;
        int n = b_num.size();
        for( int i = 2; i < n; i++ )
        {
            f[i] = f[i-1] + f[i-2];
        }
        int ans = 0;


        int has_d_one = false;
        for( int i = n-1; i >= 0; i-- )
        {
            if( b_num[i] )
            {
                ans += f[i];
                if( i < n-1 )
                {
                    if( b_num[i+1] )
                    {
                        has_d_one=true;
                        break;
                    }
                }

            }
        }
        
        //判断一下num自身是否含连续1
        //if( !( tmp & (tmp<<1) ) )
        //{
        //    ans++;
        //}
        if( !has_d_one )
        {
            ans++;
        }
        return ans;
    }