My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
 
       
// N = number of bits

       
unsigned int bits = 5;
       
 
       
// find all valid results

       
unsigned long long search(unsigned long long history, unsigned long long sequence)
       
{
       
  // bitmask for all relevant bits
       
  const unsigned int Mask = (1 << bits) - 1;
       
 
       
  // seen all 2^bits bit combinations ?
       
  unsigned long long allBits = (1ULL << (1 << bits)) - 1;
       
  if (history == allBits)
       
  {
       
    // remove lowest bits (which are all zeros)
       
    sequence >>= bits - 1;
       
    return sequence;
       
  }
       
 
       
  // shift most recent bits one position to the left, remove highest bit
       
  unsigned int next = (sequence << 1) & Mask;
       
 
       
  // two options for the following value
       
  unsigned int zero = next;
       
  unsigned int one  = next + 1;
       
 
       
  // sum of all found sequences
       
  unsigned long long result = 0;
       
 
       
  // check "zero"
       
  if ((history & (1ULL << zero)) == 0)
       
    result += search(history | (1ULL << zero),  sequence << 1);
       
 
       
  // check "one"
       
  if ((history & (1ULL << one )) == 0)
       
    result += search(history | (1ULL << one ), (sequence << 1) | 1);
       
 
       
  return result;
       
}
       
 
       
int main()
       
{
       
  std::cin >> bits;
       
  std::cout << search(1, 0) << std::endl;
       
  return 0;
       
}

This solution contains 10 empty lines, 10 comments and 1 preprocessor command.