読者です 読者をやめる 読者になる 読者になる

Javaで簡潔ビットベクトル(7)

Java

さて、前回までで、表引きによってSBの範囲内の1の数を高速に数えれるようになりました。

しかし、まだ達成できていないことがあります。
SBの範囲内の任意の位置の1の数を高速に数える方法です。

例えば、以下のようなビット列が存在し、

+------24-31------+------16-23------+-------8-15------+-------0-7-------+
| 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 |
+-----------------+-----------------+-----------------+-----------------+

0-10bitの範囲の1の数を数えたいとしましょう。

ちなみに、32bit分のrank値は、以下の処理で数えることができます。

int rank32 = TABLE[ (WORD >> 24) & 0xff )
           + TABLE[ (WORD >> 16) & 0xff )
           + TABLE[ (WORD >>  8) & 0xff )
           + TABLE[  WORD        & 0xff );

これをメソッド化してみましょう。

int rank32( int word ) {
	return TABLE[ (word >> 24) & 0xff )
             + TABLE[ (word >> 16) & 0xff )
             + TABLE[ (word >>  8) & 0xff )
             + TABLE[  word        & 0xff );
}

入力した32bitの値のrank値を数えるメソッドです。

さて、このメソッドに先ほどの32bitのビット列を与えると、16という1のrankの値を返してくれます。

しかし、今、欲しいのは、0-10bitのrank値である6です。

これを先ほど定義したrank32というメソッドから求めるにはどうすればいいでしょうか?

やり方はいろいろあると思いますが、ここでは、マスク処理によって実現してみましょう。

以下のようなマスクパターンを用意します。

+------24-31------+------16-23------+-------8-15------+-------0-7-------+
| 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 1 1 1 | 1 1 1 1 1 1 1 1 |
+-----------------+-----------------+-----------------+-----------------+

そうです。0-10bitに1が立っており残りの11-31bitがすべて0のマスクパターンです。
このマスクパターンを使えば、どのような32bitのビット列であっても0-10bitの値を取り出すことができそうです。

さて、実際には、以下のような32bit分のマスクパターンを使って、処理します。

int MASK_TABLE = new int [] {
		0x00000001, 0x00000003, 0x00000007, 0x0000000f,
		0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff,
		0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff,
		0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff,
		0x0001ffff, 0x0003ffff, 0x0007ffff, 0x000fffff,
		0x001fffff, 0x003fffff, 0x007fffff, 0x00ffffff,
		0x01ffffff, 0x03ffffff, 0x07ffffff, 0x0fffffff,
		0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff
};

このマスクパターンのテーブルは添え字が値に対応し、その値のマスクパターンを得ることができます。

例えば、20を入力すると、0-20bitを取得することができるマスクパターンである「0x001fffff」を得ることができます。
コードで書くと以下のような感じです。

int rank = rank32( word & MASK_TABLE[ 20 ] );

簡単ですね。

さて、これで高速なrankを実装する準備が整いました。
次回からは、高速なrankを実際にJavaでコーディングして実現していきます。