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

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

Java

簡潔データ構造で重要なビットベクトルをJavaで実現することを考えてみる。
というか、実際に実装してみる。

まず、ビットベクトルとは何か?について説明してみる。

ビットベクトルとは、

[ 0, 1, 0, 0, 1, 0, 1, ... ]

上記のようなひたすら0と1が並んだデータ構造である。

なので、例えば、4バイトの領域があれば、32個の0と1の並びを表現できる。

C/C++の場合は、簡単で、

unsigned int array[1000];

とか宣言しとけば、32 * 1000 = 32000個の0と1の並びを表現できることになる。
つまり、メモリ空間に余裕があれば、いくらでもビットベクトルを拡張することができる。

ビットを立てるのも簡単で、立てたい位置をposとすると、posが31以下の場合は、

array[0] = array[0] | ( 1 << pos );

のようにする。
ただし、arrray[0]が0で初期化されているとする。
また、LSBでの格納を前提にしている。

もっと汎用的に32以上の場合も扱いたい場合は、

unsigned int index = pos / 32;
unsigned int newPos = pos % 32;
array[index] = array[index] | ( 1 << newPos );

とすればあらゆる位置にビットを立てることができる。

このように、C/C++では、簡単だがJavaだとどうなるのか?について考えてみようと思う。
特に、ビットベクトルを使う場面というのはとにかくメモリを節約したい時だと思われる。
なので、より省メモリにJavaで実現できるように検討してみることとする。