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

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

Java

今週は、仕事が忙しく、週末まで更新できませんでした。

まぁ、それはさておき、今回は、表引きを利用したselectを実際に実装してみます。

まず、rankの時と同じように、selectの表引き用の表を作るところから行います。
BitVectorUtilityクラス(ユーティリティクラス)に以下のようなメソッドを定義します。

public static void output1ByteSelect() {
...
}

今回は、わかりやすくするために、前回の記事で説明した2次元配列をナイーブに表現してみます。
性能を考慮した場合は、1次元の方が良いと思います。
というのも、Javaの2次元配列は、おそらくポインタ配列なので、参照時に連続領域ではない部分を参照しているので、若干コストがかかっていると思います。
検証していないので、あくまで想像の範囲内なので、あまり気にしないでください。
ただまぁ、今回は、ナイーブに2次元配列で実現してみます。

以下のようなメソッドを作ります。

public static void output1ByteSelect() {
	
	// 1バイトで表現できる文字数分ループする。
	for ( int number = 0; number < VOCABULARY_SIZE; number++ ) {
		int currentPos = 0;
		int counter = 8;
		System.out.print("{ ");
		// 1の数ごとの1の位置を出力する。
		for ( int num = 0; num < 8; num++ ) {
			boolean isExisted = false;
			for ( int pos = currentPos; pos < 8; pos++ ) {
				int bit = 1 & ( number >> pos );
				currentPos = pos + 1;
				if ( 1 == bit ) {
					System.out.printf("%d", pos + 1);
					isExisted = true;
					break;
				}
			}
			
			// 1の数に対応する位置が存在しない場合は、0を出力しておく。
			if ( !isExisted ) {
				System.out.printf("%d", 0);
			}
			
			counter--;
			if ( 0 < counter ) {
				System.out.print(",");
			}
			
		}
		System.out.print(" },");
		System.out.println();
	}
	
}

また、このメソッドを実行した出力結果は、以下のようになります。

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

最後のカンマを消すと、Javaの2次元配列として使えます。

では、BitVectorクラスにrankの時と同じように定義してみましょう。

以下のように定義できます。

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

長いですね。
次回からは省略します。
rankの時と同様にスタティックイニシャライザを使っています。
さて、きちんとselectの表引きが実現できるでしょうか?
やってみましょう。
2次元配列の2次元目は、1の数を表現していますが、配列の添え字は0からなので、1の数が1つの場合は、0番目の添え字で表現されています。
また、1の数が2つの場合は、1番目の添え字で表現されています。残りは同様の規則で表現されています。

例えば、前回と同じ例の「161=10100001」の場合は、以下のようになっています。
ただし、×は0で表現しています。

SELECT_TABLE[161][0] = 1
SELECT_TABLE[161][1] = 6
SELECT_TABLE[161][2] = 8
SELECT_TABLE[161][3] = 0
SELECT_TABLE[161][4] = 0
SELECT_TABLE[161][5] = 0
SELECT_TABLE[161][6] = 0
SELECT_TABLE[161][7] = 0

8bitのビット位置を1-8で表現しています。前回と違い位置を0-7では表現していませんが、1つずれているだけなので、本質的には変わりありません。

ちゃんとできていますね。
さて、これで、8bitのビットベクトルのselect値を高速に求めることのできる表が手に入りました。

次回は、この表を使った表引きを利用したselect操作の実装を行います。