leetcode-go/leetcode/hard/600.non-negative-integers-without-consecutive-ones.go

func findIntegers(num int) int {
	f := make([]int, 31)
	f[0], f[1] = 1, 2
	for i := 2; i < 31; i++ {
		f[i] = f[i-2] + f[i-1]
	}
	cnt, pre := 0, 1
	for k := 30; 0 <= k; k-- { // The highest bit is the sign of int32.
		if (num>>uint(k))&1 == 1 {
			cnt += f[k]
			if pre == 1 {
				return cnt
			}
			pre = 1
		} else {
			pre = 0
		}
	}
	return cnt + 1 // Means num itself is also valid.
}