Non-negative Integers without Consecutive Ones

lcpy gen -n 600   # by problem number
lcpy gen -s non_negative_integers_without_consecutive_ones   # by problem name

Input: n = 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.

Input: n = 1
Output: 2

Input: n = 2
Output: 3

class Solution:
    # Time: O(log n)
    # Space: O(log n)
    def find_integers(self, n: int) -> int:
        bits = bin(n)[2:]
        fib = [1, 2]
        while len(fib) < len(bits):
            fib.append(fib[-1] + fib[-2])

        count = 0
        prev_bit = 0
        for i, bit_char in enumerate(bits):
            if bit_char == "1":
                count += fib[len(bits) - i - 1]
                if prev_bit == 1:
                    count -= 1
                    break
                prev_bit = 1
            else:
                prev_bit = 0
        return count + 1