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

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

Java

では、前準備は整ったので実装していこうと思います。

今回は、8bitの1のrank値を返すテーブルを作成してみようと思います。
具体的には、32bitの1のrank値を返すメソッドで利用しているTABLE配列のことです。

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

TABLE配列は、0-255(8bit)の値を添え字とする場所に、その添え字を8bitの2進数で表現した時の1の数を格納しているテーブルです。
例えば、以下のような感じです。

TABLE[0] = 00000000 = 0
TABLE[1] = 00000001 = 1
TABLE[2] = 00000010 = 1
TABLE[3] = 00000011 = 2
...
TABLE[255] = 11111111 = 8

簡単ですね。

では、作ってみましょう。
まずは、8bitの値ごとに1の数を出力するメソッドを作ってみます。
以下のような感じです。

public static void output1ByteRank() {
	for ( int number = 0; number < 256; number++ ) {
		// 8bitをループして1の数を数える。
		int rank = 0;
		for ( int shift = 0; shift < 8; shift++ ) {
			int word = number;
			word = 1 & ( word >> shift );
			if ( 1 == word ) {
				++rank;
			}
		}
			
		if ( 0 < number && 0 == (number % 8) ) {
			System.out.println();
		}
			
		if ( 0 == (number % 8) ) {
			System.out.print( rank + "," );
		} else if ( 255 == number ) {
			System.out.print( " " + rank );
		} else {
			System.out.print( " " + rank + "," );
		}
			
	}
	System.out.println();
}

このメソッドは、BitVectorクラスには必要のないメソッドなので、適当なユーティリティクラスにでも実装しておいてください。
TABLE配列を作るための8bitの値ごとの1のrank値を計算するためだけに必要なメソッドです。

さて、実際にMainクラスから実行してみましょう。
以下のような数値の列が出力されてたでしょうか?

0, 1, 1, 2, 1, 2, 2, 3,
1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7,
5, 6, 6, 7, 6, 7, 7, 8

この数値列をJavaのスタティック配列として利用します。
以下に実装例を示します。

// 1バイトの値のrank値
static final int RANK_TABLE[];
static {
	RANK_TABLE = new int [] {
		0, 1, 1, 2, 1, 2, 2, 3,
		1, 2, 2, 3, 2, 3, 3, 4,
		1, 2, 2, 3, 2, 3, 3, 4,
		2, 3, 3, 4, 3, 4, 4, 5,
		1, 2, 2, 3, 2, 3, 3, 4,
		2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5,
		3, 4, 4, 5, 4, 5, 5, 6,
		1, 2, 2, 3, 2, 3, 3, 4,
		2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5,
		3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5,
		3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6,
		4, 5, 5, 6, 5, 6, 6, 7,
		1, 2, 2, 3, 2, 3, 3, 4,
		2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5,
		3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5,
		3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6,
		4, 5, 5, 6, 5, 6, 6, 7,
		2, 3, 3, 4, 3, 4, 4, 5,
		3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6,
		4, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 5, 4, 5, 5, 6,
		4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7,
		5, 6, 6, 7, 6, 7, 7, 8
	};
}

スタティック配列を宣言し、スタティックイニシャライザで初期化しています。

さて、ちゃんと目的を達成できる配列になっているでしょうか?

RANK_TABLE[0] = 0
RANK_TABLE[1] = 1
RANK_TABLE[2] = 1
RANK_TABLE[3] = 2
...
RANK_TABLE[255] = 8

ちゃんとできていますね。

さて、これで8bitの値の1のrank値を高速に取得できるテーブルを作成することができました。

次回も引き続き高速なrankの実装を行っていきます。