定数時間MSBアルゴリズム - Qiita1-4ビット目yyyyはxxの値によって変わりますが、フラグの値は$X$のMSBと$A$中の１の位置で決まります。$A$の１が$X$のMSBより左にあるとフラグは０、さもなければフラグは１です。よって$X$に対してこの引き算を全部試せば、MSBの数だけ１が立ったフラグが手に入ることになります。 これを利用して$X’$を作っているのが下の図です。$X$にフラグをつけて√w個コピーしたあと、フラグで区切られた各区間（ブロック）に対して上記の引き算を一度に実行し、その後yyyyの部分をビットマスクで0クリアしたのが$X'$となります。$X'$のビット長は$\sqrt{w}(\sqrt{w}+1)=w+\sqrt{w}$なので、２ワード上で演算すれば$X'$は定数時間で計算できるというわけです。 X'の１を定数時間で数える方法について １が立っているビットを定数時間で数えるのは結構難しいのですが、
Redirecting…
