// YER algorithm for the perfect shuffle, by Frank Ruskey

#include<stdint.h>
#include<stdio.h>
#include<time.h>

void NT( int nn, int N ) {
  uint64_t x,y=0ULL,z,p;
  for (x = 1ULL; x < (1ULL<<nn); ++x) {
     z = x & -x;
     z = z & ~(z>>1ULL);
     double f64 = (double)z;
     p = (*(( (uint64_t *) &f64 )) >> 52) - 1023ULL;
     y = p==N ? x : y - (1ULL<<N) + (1ULL<<N-p) + (1ULL<<N-p-1ULL);
     if (x < y); // printf( "A[%llu] :=: A[%llu]\n", x, y );
  }
}

int main( int argc, char *argv[] ){
  int n = atoi(argv[1]);
  printf( "PHASE ONE\n" );
  clock_t tic = clock();
  NT( n, n-1 );
  printf( "PHASE TWO\n" );
  NT( n, n   );
  clock_t toc = clock();
  printf("Elapsed: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC);
  return(0);
}