フラグチェック

　大量の、互いに独立なビットフラグをチェックし、それぞれフラグが立っていたら(あるいは立っていなかったら) ある特定の処理を行う、というコードを書くことはよくある。

　「イベントループ」と言われるものの一番コアなループは、結局このように作られている。たとえば「シフトキーを押しながらマウスをクリック」などという状態を表現するには、シフトキー、マウスのクリックのそれぞれに対してビットを割り当て、その状態を監視して、必要な組み合わせに対してコールするべき関数を決定するわけだ。

　当然、この場合問題になるのが、どうやって「どの1ビットが立っているのか」を高速に検出するかである。

　例えば 16 種類のイベントがあるなら、このイベントフラグは全部で 16 bit のはずなので、大抵の場合どのイベントが成立しているのかを調べる「フラグチェック」は

    for ( i = 0; i < 16; i++ ) {
        event = flag & ( 1 << i );
        switch ( event ) {
        case HOGE: .... break;
        case HAGE: .... break;
        .....
        default:break;
        }
    }

のようなプログラムで実装されることになる。しかし、これだとイベントがたった１つでも16個のフラグ全部を丁寧に見て回ることになる。イベントの数が増え、かつその発生率が低い場合、これは効率が悪い。

　ある整数のレジスター x の最も低位のビットを返す技法がある。

x and ((bitwize_not x) + 1)

という計算は、『加算における繰り上がり』を巧妙に利用して LSB に最も近いビットのみを 1 にする。ちなみに全て 0 の場合、この計算の結果も 0 になる。

　この技法を応用すると、この「フラグチェック」ルーチンは次のようになる。

    while ( flag ) {
	event = flag & (( ~flag ) + 1 );
	flag	^= event;
	switch( event ) {
	.....
	}
    }

このコードの場合、ループ回数は純粋に 1 が立っているフラグの数だけ、つまりイベントの数だけに制限される。ちなみに switch 文の中身は、 binary tree を用いる方法である程度高速化は可能だが、圧倒的に有利な方法は見つかっていない。

　ちなみにこの逆、つまり単純な算術演算と論理演算だけを用いて MSB に最も近いビットのみを 1 にする方法は見つかっていない。このためと、switch() 文高速化のために、
「MSB に最も近いビットの bit id を返す命令」
を備えた CPU は存在する(PowerPC もその一つだ)。