tools/log2.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3
   4 typedef unsigned long long ullong;
   5
   6 char seen[64];
   7 ullong rbg = 0x1e0298f7a7e;
   8
   9 int
  10 bit()
  11 {
  12         int bit;
  13
  14         bit = rbg & 1;
  15         rbg >>= 1;
  16         return bit;
  17 }
  18
  19 int
  20 search(ullong n, int b, ullong *out)
  21 {
  22         int i, x;
  23         ullong y, z;
  24
  25         if (b == 64) {
  26                 *out = n;
  27                 return 1;
  28         }
  29
  30         x = 63 & ((n << (63 - b)) >> 58);
  31         assert(!(x & 0) && x <= 62);
  32         y = bit();
  33
  34         for (i=0; i<2; i++) {
  35                 z = x | (y << 5);
  36                 if (!seen[z]) {
  37                         seen[z] = (63-b)+1;
  38                         if (search(n | (y << b), b+1, out))
  39                                 return 1;
  40                         seen[z] = 0;
  41                 }
  42                 y ^= 1;
  43         }
  44
  45         return 0;
  46 }
  47
  48 int
  49 main()
  50 {
  51         ullong out;
  52         int i;
  53
  54         if (search(0, 0, &out)) {
  55                 printf("0x%llx\n", out);
  56                 for (i=0; i<64; i++) {
  57                         printf((i&7) == 0 ? "\t" : " ");
  58                         printf("%2d,", seen[i]-1);
  59                         if ((i&7) == 7)
  60                                 printf("\n");
  61                 }
  62         } else
  63                 puts("not found");
  64 }