自然数の対を自然数に写像する関数（ビット演算バージョン）を作ってみた

目標

自然数の対を自然数に射影する関数（全単射）それとRubyで九九を作ってみた を受け、逆写像が容易に作れる写像を考えました。

ビット演算

二つの非負整数を2進数で表し、各ビットを交互に並べていけば、どんな組合せでも必ず一意な結果が得られます。

例えば、0x9 と 0x35 という整数の組を考えたとき、前者は 001001、後者は 110101 です。これらを交互に並べた 101001100011 が結果となります。

この方式であれば、逆変換も自明です。

コード

とりあえずCで書いてあります。

普通の再帰で実装していますが、容易に末尾再帰にもできるし、単純なループにもできます。ビット長がわかっていれば、各ビットを取り出してそれぞれシフトして、すべての論理和をとるという単一の式でも書けます。

ただ、ハードウェアなら配線一発かと思うと、ソフトウェアでのビット操作は本当に効率悪いですね。

twoint2one.c

# include <stdio.h>

// y=110101, x=001001 => 10 10 01 10 00 11
int
twoint2one(int x, int y) {
  if (x == 0 && y == 0) {
    return 0;
  } else {
    return twoint2one(x>>1, y>>1)<<2 | (y&1)<<1 | x&1;
  }
}

// 10 10 01 10 00 11 => y=110101, x=001001
void
oneint2two(int *x, int *y, int n) {
  if (n == 0) {
    *x = 0;
    *y = 0;
  } else {
    oneint2two(x, y, n>>2);
    *x = *x<<1 | n&1;
    *y = *y<<1 | (n&2)>>1;
  }
}

int
main(void) {
  int x, y;

  printf("0x%x\n", twoint2one(0x09, 0x35)); // = 0xa63
  oneint2two(&x, &y, 0xa63);
  printf("0x%x, 0x%x\n", x, y); // = 0x9, 0x35

  printf("   ");
  for (x = 0; x < 10; x++) {
    printf("%3d ", x);
  }
  printf("\n");

  for (y = 0; y < 10; y++) {
    printf("%2d ", y);

    for (x = 0; x < 10; x++) {
      printf("%3d ", twoint2one(x, y));
    }
    printf("\n");
  }

  return 0;
}

出力は次のようになります。

0xa63
0x9, 0x35
     0   1   2   3   4   5   6   7   8   9
 0   0   1   4   5  16  17  20  21  64  65
 1   2   3   6   7  18  19  22  23  66  67
 2   8   9  12  13  24  25  28  29  72  73
 3  10  11  14  15  26  27  30  31  74  75
 4  32  33  36  37  48  49  52  53  96  97
 5  34  35  38  39  50  51  54  55  98  99
 6  40  41  44  45  56  57  60  61 104 105
 7  42  43  46  47  58  59  62  63 106 107
 8 128 129 132 133 144 145 148 149 192 193
 9 130 131 134 135 146 147 150 151 194 195