綾小路龍之介の素人思考

ビットアレイの確保

100個のビットスロットを持つビットアレイが必要な場合を考える。mallocの引数は必要なバイト数なので、100ビットが何バイトか計算する必要がある。

size_t bitarray_bit = 100;

1バイト(コンピュータが1度に取り扱える情報量の最小単位)が何ビットかはコンピュータ(処理系)に依存するが、そのためにCHAR_BITというマクロが定義されている。C言語ではchar型が、論理的にコンピュータが扱える最小単位(つまりどんなコンピュータでも1バイト)、ということで定義されているので、char型の配列をビットアレイとして使うことが多い。したがってどんなコンピュータでも1バイトはCHAR_BITビットである。ということで、下のようにかける。

size_t bitarray_byte = (bitarray_bit / CHAR_BIT) + 1;

例えば、bitarray_bitが0からCHAR_BIT-1の時、bitarray_byteは1。それぞれの対応は下のような感じ。

| bitarray_bit                 | bitarray_byte
|          0 -- 1*CHAR_BIT - 1 | 1
| 1*CHAR_BIT -- 2*CHAR_BIT - 1 | 2
| 2*CHAR_BIT -- 3*CHAR_BIT - 1 | 3
| 3*CHAR_BIT -- 4*CHAR_BIT - 1 | 4

というわけで、bitarray_bitビットのビットアレイbitarrayを確保するにはbitarray_byteを引数として下のようにmallocで確保する。

char *bitarray = (char *)malloc(bitarray_byte);

確保されたビットアレイの全ビットをゼロで埋めるにはmemsetを使うが、memsetの使い方には注意が必要。とにかくmemsetの実装例を見ておくのが最適。言いたいのは、memsetの第1引数はどんな型の変数の配列もとれるが、memsetの中ではこれをunsigned charの配列として取り扱う。さらに第2引数はint型だが、これをmemsetの中でunsigned int型に型変換して取り扱う。このようにして、第1引数に与えられた配列の先頭アドレスから、sizeof(unsigned char)バイトだけポインタの位置をずらしながら、unsigned charに型変換された第2引数の値を書き込む。ということをしている。したがって、ビットアレイのゼロクリアは、下のようにかける。

memset( bitarray, 0, bitarray_byte);

ちなみに、全部のビットを立てるために下のように書くのは間違い。第2引数がunsigned charにキャストされることを考えれば下のコードは1バイトのメモリ領域の全部を1にしてはいない。

memset( bitarray, 1, bitarray_byte);

正しくは、第2引数に2**CHAR_BIT-1つまりUCHAR_MAXを指定する必要がある。

memset( bitarray, UCHAR_MAX, bitarray_byte);
ビットアレイ
http://d.hatena.ne.jp/XuHuang/20080623/1214194703
memset
http://www.bohyoh.com/CandCPP/C/Library/memset.html
memset
http://ja.wikipedia.org/wiki/Memset

ソーシャルブックマーク

  1. はてなブックマーク
  2. Google Bookmarks
  3. del.icio.us

ChangeLog

  1. Posted: 2007-07-17T01:03:59+09:00
  2. Modified: 2007-07-17T03:55:11+09:00
  3. Generated: 2017-10-16T23:09:17+09:00