Going through all Bit Strings with no 11 in it (no consecutive 1s)

Question

My question is very simple: How can i (efficiently) go through all Bitstrings which don't contain two consecutive 1s?

So for instance, all Bitstrings of length 3 with no consecutive 1s are: 000, 001, 010, 100, 101.

I need this to be efficient for Bitstrings with length 48.

Cheers!

Edit: Solved it finally: This (unoptimized) code does the job:

template< std::size_t N >
bool next( std::bitset<N>& vec )
{
    if( !vec.test(2) && !vec.test(1) )
    {
        vec[1] = true;
        return true;
    }

    for( std::size_t i = 0; i != N - 2; ++i )
        if( vec.test(i) && !vec.test(i+1) && !vec.test(i+2) )
        {
            vec[i] = false;
            vec[i+1] = true;
            for( auto i2 = 1; i2 != i; ++i2 )
                vec[i2] = false;
            return true;
        }

    if( vec.test(N-2) && !vec.test(N-1) )
    {
        for( auto i2 = 1; i2 != N-1; ++i2 )
            vec[i2] = false;

        vec[N-1] = true;

        return true;
    }

    return false;
}

Answer 1

I don't know if this is the sort of thing you are interested, I don't know how to program yet. But you can figure it out "recursively".

For instance, for the problem where you want to find the lists of length $3$ we will need the lists of length $1$ ($1$ and $01$) and the lists of size $2$ ($00$,$01$,$10$) .Now we shall separate the lists of size $3$ into the lists that end in $1$ and the lists that end in $0$.

The lists that end in $1$ are simply the lists of size $1$ with the $01$ added to the very end (so you get $101$ and $001$).

The lists that end in $0$ are simply the lists of size $2$ with the $0$ added to the end so you get $000,010,100$.

If you are interested in counting them you can also use the previous recursive idea. Denote by $f(n)$ the number of lists with no consecutive $1$'s. Then we get $f(n+2)=f(n+1)+f(n)$ This recursion is just a Lucas, or Fibonacci kind of recurrence. In fact $f(n)$ is just $F_{n+2}$(the $n+2$ Fibonacci number).