C Sharpens you up

http://qiita.com/yuba に移しつつあります

整数を可逆スクランブルする

アルゴリズム

2年前につぶやいた内容の詳しい説明。

整数を、暗号ライブラリ使うほどじゃないんだけどスクランブルしたいことってあるんですよね。たとえば、IDを連番で振ってるんだけど連番だってことがユーザーにわかってしまうと具合が悪いとか。そういうときの簡単なスクランブル方法です。ただし、符号なし整数でしか使えないのでこの時点でJavaは対象外ごめんなさい。

まず32ビット整数版のC,C++,C#で動くコードです。

uint Scramble(uint v)
{
	// 奇数その1の乗算
	v *= 0x1ca7bc5b;

	// ビット逆順
	v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
	v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
	v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
	v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
	v = ( v >> 16             ) | ( v               << 16);

	// 奇数その2（奇数その1の逆数）の乗算
	v *= 0x6b5f13d3;
	return v;
}

与えた整数を、一件全然無関係な整数にして返します。それをもう一回食わすとあら不思議、もとの整数が出てきます。

100 => 0x77218a64 => 100
101 => 0xccbd2ff6 => 101

仕組みを説明していきます。

32ビット整数の逆数

0x1ca7bc5b * 0x6b5f13d3を計算してみてください。32ビット整数にとると1になります。
0x1ca7bc5bと0x6b5f13d3は32ビットの世界では逆数の関係にあるわけです（2^32を法とする逆数と言います）。

どんな奇数にもその逆数は簡単に用意できます。手順は「ユークリッドの互除法」で検索。続きはWebで。

だからv * 0x1ca7bc5b * 0x6b5f13d3 == vです。
さてこの時点で早い話、0x1ca7bc5bをかけるだけでスクランブル、それに0x6b5f13d3をかけて復元、ってだけでも成立しています。

それだけで済ませないのはなぜかというと。

下位桁の固定を防ぐ

乗算の結果をご覧ください。

0x1 * 0x1ca7bc5b = 0x1ca7bc5b
0x2 * 0x1ca7bc5b = 0x394f78b6
0x100000 * 0x1ca7bc5b = 0xc5b00000
0x200000 * 0x1ca7bc5b = 0x8b600000

もとの数が少し変わっただけで出てくる数字の見た目はがらっと変わる半面、もとの数が大きな数で上位桁が変わっただけだと、出てきた結果も下位桁が変わらないですね。乗算では下位桁が固定する性質があるのです。

場合によってはこれはいただけません。

そこで、奇数を乗算してからビットの上下をすべてひっくり返します。すると下位桁は変わっていて上位桁だけ固定された状態になっているので、ここでもう一度奇数を乗算します。これでまんべんなくばらけました。

2回目にかける奇数を、1回目の逆数にしてみましょう。するとあら便利、関数全体として自分自身の逆関数になってますね！

注意点 2013/06/21 追記

このScramble関数にはScramble(0) == 0という自明な不動点があります。ゼロ対策の加減算ステップ入れるか、ゼロを食わせることがない状況で使うかしていただきますよう。