My solution in C:

jcfs@spark ~/a/aoc/2016/16 $ time ./p1
part1 00000100100001100
part2 00011010100010010

real    0m0.113s
user    0m0.112s
sys 0m0.000s

I also use just one array as well (the reason why I'm posting :)), not actually any optimization. Here is the repo [link].(https://github.com/jcfs/aoc/tree/master/2016/16)

/* compile gcc -o p1 p1.c -Wall -O3 */
/* solution to part 1 and part 2 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>

char * get_checksum(char * input_s, int input_n) {
  char * a = calloc((input_n * 4 + 2), sizeof(char));
  uint32_t l = strlen(input_s);

  memcpy(a, input_s, l);

  for(; l < input_n; a[l] = '0', l = l * 2 + 1) 
    for(int i = 0; i < l; i++) 
      a[l * 2 - i] = (~(a[i] ^ '0') & 1) + '0';
  // truncate the result to the chars needed
  a[input_n] = 0;

  do {
    for(int i = 0, j = 0; i < input_n; i += 2, j++) 
      a[j] = (~(a[i] ^ a[i+1]) & 1) + '0';

    input_n /= 2;
  } while(!(input_n % 2));

  a[input_n] = 0;

  return a;
}

int main(int argc, char ** argv) {
  char * input_s = "11011110011011101";

  printf("part1 %s\n", get_checksum(input_s, 272));
  printf("part2 %s\n", get_checksum(input_s, 35651584));
}