個人的に一番速いと思うナベアツ問題のプログラム

gistfile1.txt

#include <unistd.h>
#define BUFSIZE 65536
char buf[BUFSIZE];
int
main(int argc, char *argv)
{
  unsigned int i;
  unsigned int ketapos = 0;
  unsigned int bufpos = 0;
  i = 0;
  while (i < 0x1000000) {
    i++;
    if ((i & 0xf) > 0x9) {
      i += (0x10 - 0xa);
      ketapos |= 1;
      if ((i & 0xff) > 0x9f) {
        i += (0x100 - 0xa0);
        ketapos |= 2;
        if ((i & 0xfff) > 0x9ff) {
          i += (0x1000 - 0xa00);
          ketapos |= 4;
          if ((i & 0xffff) > 0x9fff) {
            i += (0x10000 - 0xa000);
            ketapos |= 8;
            if ((i & 0xfffff) > 0x9ffff) {
              i += (0x100000 - 0xa0000);
              ketapos |= 16;
              if ((i & 0xffffff) > 0x9fffff) {
                ketapos |= 32;
                i += (0x1000000 - 0xa00000);
              }
            }
          }
        }
      }
    }
    unsigned int k = i;
    k ^= 0xcccccccc;
    k &= (k >> 1);
    k &= (k >> 2);
    k |= (k >> 16);
    k |= (k >> 8);
    k |= (k >> 4);
    k &= 1;
    unsigned int d = i;
    d = ((d >> 2) & 0x33333333) + (d & 0x33333333);
    d = ((d >> 4) & 0x07070707) + (d & 0x07070707);
    d = ((d >> 8) & 0x000f000f) + (d & 0x000f000f);
    d = (d >> 16) + (d & 0x1f);
    d = ((d >> 2) & 0x33333333) + (d & 0x33333333);
    d = ((d >> 4) & 0x07070707) + (d & 0x07070707);
    d = ((d >> 2) & 0x33333333) + (d & 0x33333333);
#if 0
    if (k || d == 3)
      printf("AHO\n");
    else
      printf("%x\n", i);
#else
    if (bufpos > BUFSIZE - 20) {
      write(STDOUT_FILENO, buf, bufpos);
      bufpos = 0;
    }
    if (k || d == 3) {
      buf[bufpos++] = 'A';
      buf[bufpos++] = 'H';
      buf[bufpos++] = 'O';
    }
    else {
      switch (ketapos) {
      case 63:
	buf[bufpos++] = '0' + (i >> (4 * 6));
      case 31:
	buf[bufpos++] = '0' + ((i >> (4 * 5)) & 0xf);
      case 15:
	buf[bufpos++] = '0' + ((i >> (4 * 4)) & 0xf);
      case 7:
	buf[bufpos++] = '0' + ((i >> (4 * 3)) & 0xf);
      case 3:
	buf[bufpos++] = '0' + ((i >> (4 * 2)) & 0xf);
      case 1:
	buf[bufpos++] = '0' + ((i >> (4 * 1)) & 0xf);
      case 0:
	buf[bufpos++] = '0' + (i & 0xf);
      break;
      }
    }
    buf[bufpos++] = '\n';
#endif
  }
  write(STDOUT_FILENO, buf, bufpos);
  return 0;
}