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>
       
#include <queue>
       
#include <vector>
       
#include <functional>
       
 
       
// bit sequence

       
typedef unsigned char Cost;
       
 
       
// find result using a priority_queue

       
unsigned long long queue(unsigned int limit)
       
{
       
  std::priority_queue<Cost, std::vector<Cost>, std::greater<Cost>> codes; // min-heap instead of default max-heap
       
  // first two codes
       
  codes.push(1);
       
  codes.push(4);
       
  unsigned long long totalCost = 5; // sum of the first two codes: 1+4
       
 
       
  // until enough codes generated
       
  unsigned int numCodes = 2;
       
  while (numCodes < limit)
       
  {
       
    // pick the first
       
    auto current = codes.top();
       
    codes.pop();
       
    // add two new children codes
       
    codes.push(current + 1);
       
    codes.push(current + 4);
       
 
       
    // keep track of the cost
       
    numCodes++;
       
    totalCost += current + 1 + current + 4 - current; // same as current + 5
       
  }
       
 
       
  return totalCost;
       
}
       
 
       
// find result using a bit-length counters

       
unsigned long long array(unsigned int limit)
       
{
       
  std::vector<unsigned long long> costs(70, 0);
       
  // initial single-bit codes: "0" => weight 1, "1" => weight 4
       
  costs[1] = 1;
       
  costs[4] = 1;
       
  unsigned long long totalCost = 1 + 4;
       
 
       
  // start with the lowest weight (which is 1)
       
  auto current = 1;
       
  // number of codes that I need to generate
       
  auto remaining = limit - 2;
       
  while (remaining > 0)
       
  {
       
    // all codes "used" of the current weight ? => look at higher weights
       
    while (costs[current] == 0) // no gaps: "if" instead of "while" works as well
       
      current++;
       
 
       
    // try to process all codes of a certain weight at once
       
    auto block = costs[current];
       
    // except when I don't need all of them
       
    if (block > remaining)
       
      block = remaining;
       
 
       
    // adjust counters
       
    remaining          -= block;
       
    costs[current]     -= block;
       
    costs[current + 1] += block;
       
    costs[current + 4] += block;
       
    // weight is block * (current + 1 + current + 4 - current)
       
    totalCost          += block * (unsigned long long)(current + 5);
       
  }
       
 
       
  return totalCost;
       
}
       
 
       
int main()
       
{
       
  unsigned int limit = 1000000000;
       
  std::cin >> limit;
       
 
       
  // slow algorithm
       
  //std::cout << queue(limit) << std::endl;
       
 
       
  // fast algorithm
       
  std::cout << array(limit) << std::endl;
       
 
       
  return 0;
       
}

This solution contains 14 empty lines, 19 comments and 4 preprocessor commands.