题目很简单，小于等于n的、二进制不包含连续1的非负整数。

 

接下来我们试图举个具体的例子来分析这个问题。

假设 n 是 101001100, 它有 9 个二进制位。

为了解释方便，我们定义 F串：n 位的 F 串是 n 个不包含连续 1 的01串。

例如， 对于 n = 4，我们有 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010，一共 8 个 F串。

 

因为 n = 101001100，那么形如 0xxxxxxxx 这样的 F 串都是满足要求的。换句话说就是求 8 位的 F串有多少个

继续分析，10xxxxxxx 这样的串呢？我们不能确定那些符合要求，因此它对我们没有帮助。

101xxxxxx，这时候可以同理了，100xxxxxx这样的串又是符合我们要求的了，求 6 位的 F串有几个即可。

这样，是不是在从左往右的第 i 位发现了一个数码 1，就意味者我们就可以res += F[i-1]了呢？

直到10100[11]xx，我们发现，101000xxx 包含了 1010000xx 内的数，我们已经不必再重复计算了。

所以如果存在连续 1，我们就到此为止。

 

好难说清楚……看看就好，代码抄题解就行。