MSBを計算するアルゴリズムはいくつかあるのですが、32bitのMSBに限定した実用的で速そうなものに以下があります。
このコードを解説していきながら、ハミルトン問題について触れます。
static const unsigned char s_abyLog2[32] = {
0, 1, 28, 2, 29, 19, 24, 3, 30, 22, 20, 10, 25, 12, 15, 4,
31, 27, 18, 23, 21, 9, 11, 14, 26, 17, 8, 13, 16, 7, 6, 5
};
int GetMsbPos(unsigned int uVal)
{
/* uVal must not be 0x00000000. */
if (uVal == 0) return -1;
/* Propagates MSB to all the lower bits. */
uVal |= (uVal >> 1);
uVal |= (uVal >> 2);
uVal |= (uVal >> 4);
uVal |= (uVal >> 8);
uVal |= (uVal >>16);
/* Turns off all the bits except MSB. */
uVal >>= 1;
uVal ++;
/* Parameter uVal must be a power of 2. */
uVal = (0x07D6E531 * uVal) >> 27;
return (int)s_abyLog2[uVal & 0x1F];
}
アルゴリズムの仕様
入力は32bitです。このアルゴリズムは乗算1回のみかつ条件分岐が1回のみとなります。
このコードは32bitのMSBの位置を出力します。例えば0x0000000Fなら0-indexedなので3です。0xFFFFFFFFなら31が出力されます。
どうでもいいですが0x00000000には-1が返るようになっています。
アルゴリズムの説明
/* Propagates MSB to all the lower bits. */
uVal |= (uVal >> 1);
uVal |= (uVal >> 2);
uVal |= (uVal >> 4);
uVal |= (uVal >> 8);
uVal |= (uVal >>16);
ここでMSB以下の全てのビットを立てています。0b 001*****...*** とあれば、0b001111....11とMSB以下が全て1になります。
/* Turns off all the bits except MSB. */
uVal >>= 1;
uVal ++;
そしてここでMSBのみを1にしています。
ここまでの実行が終わると、uValは 0b00...00 1 00...00 という状態になっています。$2^{MSB}$ ですね。
この状態である整数と掛け算をすると、これはシフト操作と等価になります。これは二進数の掛け算の筆算を考えたらすんなり理解できると思います。
/* Parameter uVal must be a power of 2. */
uVal = (0x07D6E531 * uVal) >> 27;
return (int)s_abyLog2[uVal & 0x1F];
というわけで、ここで謎のマジックナンバーの 0x07D6E531 と掛けて左シフトしたあとにすぐ27右シフトして、下から 5bit だけ抽出 ( &0x1F ) して配列をみればMSBの位置がわかるみたいです。よくわかりませんね。でもここが一番おもしろいので図1を使って説明します。
このように、0x07D6E531 には 5bitの数字32種類すべてを巧妙にずらして含んでいます。この性質をもつため、どれだけシフトされたかがシフト後の結果からわかるというわけです。MSBだけシフトしていたわけなので、シフト量の情報=MSBの情報です。よってその対応を配列で持っておけば、MSBがわかるわけですね！
一般化への考察
言うまでもなく、このアルゴリズムはマジックナンバーをどう作るかが大変重要になってきます。
32bitのMSBは32種類あるので、5bitの情報。5bitの情報を32個ずらして綺麗に並べると、32+(5-1)bitで表すことができます。32bitから飛び出た4bitは全て0で後ろにつけるとすれば、0x07D6E5310 は36bitでこれを満たしますね。
では64bitのMSBはどうでしょうか？64bitのMSBは64種類、6bitの情報ですね。6bitの情報を64個ずらして並べることができるとすると、64+(6-1)bitで表現できます。同様に後ろにはみ出た5bit分は0埋めしないといけないですね。さて、そのようなマジックナンバーはあるのでしょうか？
一般化して、$w=2^s$ に対して、$w + (s - 1)$ 個のビット列で末尾 $s-1$ 個は0で、すべての連続した$s$ビットの切り出しが相異なるビット列はあるでしょうか？
$s$-bit のビット列の左1bitを削って右に新らたに足してできる$s$-bit 列は2通り考えられます。そして、すべてのbit列を一回ずつ通るような道筋を求めたいわけです。これはハミルトン路問題の特殊なケースにあたります。
ハミルトン路問題
グラフ $G=(V, E)$ が与えられたとき、全ての頂点をちょうど1度だけ通るようなパスが存在するか判定する問題。
これはNP完全問題です。
先ほどの問題は簡単な操作でハミルトン路問題に還元できます。逆はどうでしょうか？
逆の還元はできる？
こっちを示せればとてもかっこいいんですけど、思いつきませんでした…
つまり、この問題は多項式時間で解けるのかどうかわかりませんでしたし、ハミルトン路の存在性も言えませんでした。悲しいね。
かなり興味深い構造のグラフなので、研究対象として面白そうです。
誰か64bit verのマジックナンバー見つけてくれたら激アツなんだけどなぁ。まあN=64,M=126とかならゴリ押しでなんとかなったりならなかったりしそう。
追記、これはde Bruijin sequenceというやつらしく組み合わせ数学の話で結構有名なやつでした。
後日この辺の話題を証明とかさらいつつ追記しようと思います
Qiita、なぜ記事の非公開化がないんだ…
その他
このアルゴリズムを任意のbit幅に拡張した場合 $w$ ビット入力に対しメモリは $O(w)$ 使い、計算量は $O(\log w)$ だと思うんですが自信がない。
まあ任意のbit幅においてハミルトン路があるかがわからないのでなんとも言えませんが。