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

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

Java

実際にJavaに存在するデータ構造で、ビットベクトルを表現することを考えてみます。

1バイト=8bitなので、以下のような8個の要素を表現できるビットベクトルの場合は、1バイトで表現することができます。

00000000

つまり、必ずしもbit単位のデータ構造がなくてもバイト単位のデータ構造があれば代用できそうです。

Javaのデータ構造に、int型とlong型があります。
int型は、4バイトで、long型は8バイトの領域です。
C/C++系の言語と違い、Javaのint型とlong型は、環境に依存せず、領域のバイト数が決まっています。
なので、int型が環境によってサイズが異なるような事態にはなりません。

あまり詳しくないですが、コンピュータには、メモリアクセスの単位というのがあり、一般的にWORDと呼ばれます。
このWORDは、環境によって異なるのですが、32bit(4バイト)や64bit(8バイト)だったりするようです。
int型やlong型はこの性質にぴったり合致します。
なので、これらの型を使ってビットベクトルを表現します。
C/C++でも同様の選択がよくなされるようです。

今回は、以下のようにint型でビットベクトルを表現してみます。

int bitVector = 0;

int型は、4バイトなので、ビットベクトルにすると以下のように32個のビットを表現できます。

00000000000000000000000000000000

なので、4バイト単位の領域をいくつもつなげることで、32個よりも多いビットベクトルを表現することができそうです。
例えば、配列として、以下のように宣言すれば、

int bitVector[] = new int [1000];

32 * 1000 = 32000個の領域のビットベクトルが利用できます。
Javaのint型の配列は、領域を確保した時点で、自動で0に初期化されるようです。

ここまでで、ビットベクトルをバイト単位の別の型で表現することができました。

次は、任意の位置のビットに値を設定するsetBit(pos, value)メソッドについて実装してみようと思います。