```
class Solution:
def findIntegers(self, num):
"""
:type num: int
:rtype: int
"""
i = 0 # the index of next bit to process, or the number of bits we have processed
n_end_with_0 = 1 # number of values that use i bit(s), ending with 0 and have no consecutive 1s
n_end_with_1 = 0 # number of values that use i bit(s), ending with 1 and have no consecutive 1s
n = 0 # the number of values that has no consecutive 1s.
last_bit_mask = 0x1
num += 1 # Since the our algorithm only looks at numbers
# in [0, num), we add the original num by 1.
# You shall see this after reading the comments
# in the loop body
while num > 0:
# Notation:
# - x: the bit being processed in this iteration
# - p: bits before the bit x, named after prefix.
# - We call a number that has no consecutive 1's a DESIRED number
#
# In each iteration, we compute the number of values in [ p00..0, px0..0 )
# - if p is a desired number or x is 0, then 0
# - else the number is equal to the count of desired numbers in [000...0, 100...0),
# or [000...0, 011...1], this problem can be solver by DP.
num >>= 1 # note now p == num
# (x & (x << 1)): quick way to test if x has consecutive 1s, be careful with overflow.
if (num & (num << 1)) == 0 and (num & last_bit_mask) == 1:
n += n_end_with_1 + n_end_with_0
i += 1
n_end_with_0, n_end_with_1 = n_end_with_1 + n_end_with_0, n_end_with_0
return n
```