立っている最右端ビット(Right Most Bit)の位置を高速に算出する方法

2019年9月5日

ゲームのフラグ管理などで立っているビット位置を算出したい時があるかと思います。

例(1) … xxxx(中略)xxxx1000 ← 3と返したい ※xは任意

例(2) … xxxx(中略)xxx10000 ← 4と返したい

普通に考えるとループでビットシフトしてビット演算してカウントする方法を思いつくと思います。

それよりも素晴らしい「立っている最右端ビット(Right Most Bit)の位置を高速に算出するアルゴリズム」を紹介しようと思います。

使われる技術

ビット列の最右端の1を残して残りを0にするビット演算

long型のxという変数にビット列が入っているとします。

ulong y = ( ulong ) ( x & -x );

これでビット列のxの部分が0になった値がulong型の変数yに入ります。

例えば例(1)のビット列は0000(中略)00001000となります。

6ビット単位で見たとき0～63が全て含まれる特殊な数値

64ビットの「0x03F566ED27179461」という数値があります。

2進数で表記すると「0000 0011 1111 0101 0110 0110 1110 1101 0010 0111 0001 0111 1001 0100 0110 0001」となります。

この数値はM系列と呼ばれるもので、1ビットずつずらしながら6ビット単位で見ていった時に0～63の数値が順不同で含まれている特殊な数値です。

左端から最初の6ビットを見ると000000、左端から最初の1ビットを除いて6ビットをみると000001となっていることが分かると思います。

この上位6ビットをキーとして活用します。

完全ハッシュテーブルによるビットシフト数との関連付け

「0x03F566ED27179461」の上位6ビットのパターンが表す数値とビットシフト数の対応表を用意しておきます。

コードで書くと以下のようになります。

static int[] table;

table = new int[ 64 ];
ulong hash = 0x03F566ED27179461UL;
for ( int i = 0; i < 64; i++ )
{
    table[ hash >> 58 ] = i;
    hash <<= 1;
}

立っている最右端ビット(Right Most Bit)位置算出コード

先に解説した技術を組み合わせると実際のコードは以下のようになります。

※完全ハッシュテーブル（table配列）は前もって作成済みの前提

public static int GetNumberOfTrailingZeros( long x )
{
    if ( x == 0 ) return 64;

    ulong y = ( ulong ) ( x & -x );
    int i = ( int ) ( ( y * 0x03F566ED27179461UL ) >> 58 );
    return table[ i ];
}

最初のif判定は立っているビットが無い（引数が０のとき）を除外するためにあります。

xxxx(中略)xxxxxxx1の時も0を返すため、それと区別が出来なくなることを防いでいます。

yは立っている最右端ビットのみが1になった数値が入っているため、「 0x03F566ED27179461 」に掛けることにより、yの立っているビット位置に応じて「0x03F566ED27179461UL」が左にビットシフトされた数値になります。

例えば、例(1)だとyは2進数で0000(中略)00001000なので、「0x03F566ED27179461UL」を左に3ビットシフトした数値が得られます。

「0x03F566ED27179461UL」は2進数で「0000 0011 1111 0101 0110 0110 1110 1101 0010 0111 0001 0111 1001 0100 0110 0001」です。

左に3ビットシフトすると「0 0011 1111 0101 0110 0110 1110 1101 0010 0111 0001 0111 1001 0100 0110 0001 000」となります。

この数値を右に58ビットシフトすると上位6ビット「000111」が得られます。

この7という数値が完全ハッシュテーブル対応表のキー値になり、得られる値は3となります。

最後に

この64ビット版は元々ある32ビット版の拡張になります。

M系列を使用するという元々のアルゴリズムを最初に考えた人は凄いと思います。

この記事を書くにあたり以下の記事を参考にさせて頂きました。

https://siokoshou.hatenadiary.org/entries/2009/07/04

※実際のコードも引用させてもらっています。問題がございましたらご連絡下さい。