_BitScanReverse や __builtin_clz を使わないときの代替関数なので、やってることは clz (Count Leading Zeros)。■入力値の範囲が2^{32}通り(32ビット)で出力値が32通り(５ビット)なので、ざっと2^{27}分の１に情報が縮退している。■いちばんアホなアルゴリズムが2^{32}通りの if 文を書くもので、人並みの知能があれば32通りの分岐を書いて済ませるくらいはできる。■ここからが魔術の出番。ビットの折りたたみ方次第ですべての入力値を分類して出力値のひとつへと導くことができる。■仕上げの “multiplication” で上位の５ビットに情報が集約されている。繰り上がりの有無が潜在的な分岐になっているのだろう。こういうのって『Hacker's Delight』を読んだら身に付くんだろうか。■clz の出力値の０っていうのは入力値の１ビット分の情報しか持っていないけど、１になると２ビット分。２になると……。畳み込まれている情報の量が違う。これは「パリティの計算(20170620)」と対照だと思う。だからどうってことではなくて、これ以上魔術に近づけないからお茶を濁してるってだけ。■■■PDF 読んだ。(1) 元の数を加工して MSB (most significant bit) だけが立った状態にする。数値としては２のべき乗になり、この数を掛けるということはシフト演算と同じ。(2) de Bruijn 列というのは文字種(k)と文字列長(n)の２つのパラメータで特徴付けられる長さk^nの環状文字列(※末尾の次に先頭の文字が来ると考える)。パラメータに対してユニークではない。特徴は、長さ n の部分文字列を切り出したとき、どの２つとして同じものがないということ。例えば、長さ５のビット列を列挙するのに2^5=32ビット長の de Bruijn 列を用意して、任意のビットから始めて５ビットを取り出せば足りるし、余りもしないということ。(3) 1 と 2 を組み合わせるとどうなるか。de Bruijn 列に(1)の値を掛けて、固定された位置にある幅 n のビット列を読み取ると、MSB に特有の値が得られる。de Bruijn 列を触媒にすることで 2^0, 2^1,...,2^{31} だった値が、順不同ながら 0, 1,..., 31 という値に変換される。これこそが求める値。２のべき乗の掛け算(=左シフト)で仮想的にビット列を循環させるために、先頭の n ビットが 0 の de Bruijn 列を(2)で選んで、最上位の n ビットを部分列として読んでいる。■英語なのもあって一歩進むたびに「ん？」と置いて行かれそうになるんだけど、そのたびに “For example,...” と挙げられる具体例に助けられた。わかりやすい。最初から読んどけば良かった。■PDF ではこのアルゴリズムに対して、掛け算は遅い、メモリアクセス(テーブル引き)は遅い、64ビットの掛け算はもっと遅いという視点をもって性能評価を行っている。シビアだなあ。■■■@2019-07-09『ハッカーのたのしみ』に寄せられたガイ・Ｌ・スティール、ジュニアによる序文から。「２進数の加算と減算そしてことによるとビット単位の演算だけでできることは驚くほどである。キャリーの連鎖が単一のビットをその左側にある全ビットに影響させることができるという事実から、広く認識されていない形で、加算を特別強力なデータ操作演算にしている。」