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

Javaでビットベクトル(5)

Java

さて、ビットベクトルの表現方法が決まったので、BitVectorクラスにsetBit( pos, value )メソッドを実装することにします。
setBit( pos, value )メソッドはビットベクトルに対して、指定された位置(pos)に指定された値(value)を設定するメソッドです。

ここで、少しだけ問題となることがあります。
まぁ、ビット演算に慣れている人なら特に問題ないですが、私には直観的ではなかったので、書いておきます。

そもそもここまでに経緯として、ビットベクトルに適したデータ型がないため、int型で代用したビットベクトルを作ったということがあります。
なので、setBit( pos, value )メソッドのposの値が、mBitVectorの配列の添え字に対応していないということです。
つまり、

this.mBitVector[pos] = value;

とかできないわけです。
ビットベクトルを表現した配列の要素の一つは、32個のビットを表現できることになっているので、ビットベクトルを表現した配列のどの要素にposが含まれているのかを調べる必要があります。

ビットベクトルを表現した配列の要素をWORDとします。
まず、ビットベクトル内のどのWORDにsetBit( pos, value )メソッドのposが含まれるかを調べます。
以下のようにします。
ここで、posは、long型です。
また、位置なので、posは、0以上です。

// ビットを立てたいWORDがいったいどこにあるのか?
int wordPos = (int) (pos / WORD_BIT_SIZE);

整数値の割り算は、小数点の切り捨てが行われるため、上記のやり方で、対象となるWORDがどこにあるかがわかります。
WORD_BIB_SIZEは、スタティックな変数で、WORDがint型なので、32です。

例えば、pos=10の場合、10 / 32 = 0となります。
つまり、ビットベクトルの添え字が0の要素がposの対象ということがわかります。
pos=100の場合、100 / 32 = 3となります。
つまり、ビットベクトルの添え字が3の要素がposの対象ということがわかります。

ここまでで、ビットを設定したいWORDの位置を特定できました。
しかし、WORD内には、32個の候補があります。
なので、次に必要な操作は、WORD内の32個のビットのどこにビットを設定すればいいかを特定することです。
それは、以下のように、剰余を求めることで、ビットを設定すべき位置を特定することができます。

// WORD内のどの位置なのか?
int shift = (int) (pos % WORD_BIT_SIZE);

WORD_BIT_SIZE=32なので、剰余を計算することで、0-31の値が得られます。
これにより、WORD内のどの位置にビットを立てるべきかを判定することができます。

では、実際に、wordPosとshiftを使って、posの位置にビットを立ててみましょう。

まず、wordPosを使って、対象となるWORDを取り出します。

int word = this.mBitVector[ wordPos ];

次に、shiftを使って、ビットを立てたい位置にビットを立てます。
value=1の場合は、以下のようにします。

word = word | ( 1 << shift );

上記の操作は、ビット操作に慣れてないと、複雑に感じますが、難しい操作ではないです。

例えば、word=0として、shift=5とした場合は、以下のようなビットの状態です。

word:
00000000000000000000000000000000

1:
00000000000000000000000000000001

まず、「1 << shift」なので、1を5ビット左シフトするという意味です。
なので、以下のような状態になります。

00000000000000000000000000100000

これと、word=0の論理和を取れば、操作が完了するので、wordの値は以下のようになります。

word:
00000000000000000000000000100000

LSBでビットを見た時、word内のshift=5の位置にビットを立てることができたのがわかります。
シンプルですね。
value=0の場合も簡単なので、考えてみてください。

では、最後に、setBit( pos, value )メソッドの実装を以下に示します。

public void setBit( final long pTargetPos, final int pValue ) {
		
	// pPosの値のチェック
	if ( 0 > pTargetPos && this.mBitSize <= pTargetPos ) {
		// 負の長さであってはならない。
		// 格納できるビット数を超えてはならない。
		throw new MyProjectRuntimeException(new IllegalArgumentException());
	}
		
	// pValueの値のチェック
	if ( 0 != pValue && 1 != pValue ) {
		throw new MyProjectRuntimeException(new IllegalArgumentException());
	}
		
	// ビットを立てたいWORDがいったいどこにあるのか?
	int wordPos = (int) (pTargetPos / WORD_BIT_SIZE);
		
	// WORD内のどこなのか?
	int shift = (int) (pTargetPos % WORD_BIT_SIZE);
		
	int word = this.mBitVector[ wordPos ];
	if ( 1 == pValue ) {
		// 1の場合
		word = word | ( 1 << shift );
		this.mBitVector[ wordPos ] = word;
	} else {
		// 0の場合
		word = word & ~( 1 << shift );
		this.mBitVector[ wordPos ] = word;
	}
		
}

posがpTargetPosになっていますが、処理に変更にありません。
引数のエラーは、コンストラクタの時と同じように実行時例外を返しています。
valueは、0と1しかないのだから、boolean型でも良かったかもしれません。
booleanにすれば、引数チェックを一つ減らすことができます。
設計の問題ですが、今回は、クライアントから使う時に、明示的に0や1を設定させるために、このような引数にしました。

次回は、実際に、BitVectorクラスを完成させ、クライアントプログラムからテストしてみようと思います。