不包含连续的1的整数

给定一个正整数 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

根据题目描述，我们可以拿到1～n每个数字的二进制，然后计算二进制不包含连续的1的整数的数量，返回即可。但是 题目中的n的取值范围为[1,10^9]，暴力肯定会超时。

我们要计算的是[0,n]范围内数字二进制不包含连续1的个数。

假设数字n的二进制位为：1001001，如何计算范围内数字二进制不包含连续1的个数？

首先我们假设数字开头为0，数字表示为0xxxxxx。0之后的二进制可以为1，可以为0。在这种情况下，我们唯一能够 确定的就是，开头的0那一位。xxxxxx中有多少个不包含连续1数字呢？我们先记下这个子问题。

其次我们假设数字开头为1，那么1之后的二进制位必须为0。重申一下，二进制中不包含连续1的数字。那么我们可以确定 开头的两位二进制10。那么数字可以表示为10xxxxx。xxxxx中有多少个不包含连续1的数字呢？

声明一个数组dp，下标i表示长度为i的二进制。dp[i]表示该二进制位不包含连续的1的数量。由于 数字的二进制的每一位不是0就是1，如果一个二进制的开头为0，那么它的的下一位就可以选择0，或者1。如果一个二 进制的开头为1，那么它的下一位只能是0，如果是1的话就不符合题目中要求的不包含连续的1。由此可以得出：

dp[i] = dp[i - 1] + dp[i - 2]

dp[i - 1] 表示 0开头的，长度为i-1的二进制中不包含连续1的数量 dp[i - 2] 表示 10开头的，长度为i-2的二进制中不包含连续1的数量

终止条件为：

dp[0] = 1 dp[1] = 2

例如：1001001

首先要考虑： 0000000～01111111 中不包含连续1的数字的数量

然后就是：1000000～1001001 中不包含连续1的数字的数量 ( ？)

怎么求1000000～1001001 中不包含连续1的数字的数量 ( ？)呢，我们可以计算

1000000~10000111和1001000到1001001的数量。

考虑一下边界条件： 1001101，这种情况下，我们需要对每个为1的二进制位记录他的前一位二进制，如果两者都为1，那么返回false。否则返回true。

代码

func findIntegers(n int) (ans int) {
	k, dp := 32, [32]int{1, 2} // k = 32是要从2^32（最大）开始计算
	for i := 2; i < k; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}

	k = 31
	pre := 0
	for k >= 0 {
		if n&(1<<k) != 0 {
			ans += dp[k]
			if pre == 1 {
				return ans
			}
			pre = 1
		} else {
			pre = 0
		}
		k -= 1
	}

	return ans + 1
}