不含连续一的非负整数

不含连续一的非负整数

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

先考虑\(n=2^k\)，在排除0的情况下，可以发现这个结果就是斐波那契数列。

\[ \displaylines{ f(2^k) = f(2^{k-1}) + f(2^{k-2}) \\ f(1) = 1;f(2) = 2. } \]

在考虑任意\(n\)，从第一个bit开始循环，如果遇到连续的一，则可以终止循环。

\[ \displaylines{ f(b1100100) = f(b1011111)=f(b1010101) \\ = f(b1000000) + f(b10000) + f(b100) + f(b1)\\ = f(b1000000) + f(b100000) - 1 } \]

（难也不难，但通用性很差，这两个规律都要自己发现...就很浪费时间）

class Solution {
public:
    int findIntegers(int n) {
        // fibonacci
        vector<int> f, b;
        f.push_back(1);
        while (n) {
            if (n & 1) b.push_back(1);
            else b.push_back(0);
            if (f.size() >= 2) f.push_back(f[f.size() - 1] + f[f.size() - 2]);
            else f.push_back(1);
            n /= 2;
        }
        bool flag = false;
        int ans = 1; // 0 also counts
        for (int i = b.size() - 1; i >= 0; i--) {
            if (b[i]) {
                if (!flag) {
                    flag = true;
                    ans += f[i+1];
                } else {
                    ans += f[i+1] - 1; // self do not count, so -1.
                    break;
                }
            } else {
                flag = false;
            }
        }
        return ans;
    }
};