ビット演算を利用したbool型配列
こんにちは．株式会社ガラパゴスの[twitter:@kokosamu]です．
今回は毎度おなじみ[twitter:@necocen]リスペクトシリーズ*1として
ビット演算によりint型をbool型の配列として扱う方法*2を紹介します．
機器の高速化によりないがしろにされがちなビット演算ですが
これを期にbool型の配列を実現する手法として見つめ直してみてはいかがでしょうか．
解説の前に
今回の記事ではC言語を対象に解説します．
C言語のビット演算子，またビット演算自体がわからない方は
読み進める前にまずそちらを調べる*3ことをオススメします．
なお今回の記事で利用するプログラムはkksm_bit.zip 
*4です．
32bit環境での利用を前提としていますので
それ以外の場合は BIT_SIZE の値を変更してください．
またデバッグ用にshow_bit関数を用意しています．
今回の記事とは直接には関係しないため解説は省略します．
配列の宣言
まずは配列の宣言方法についてです．
unsigned neco; neco = 0; show_bit(neco); /* 00000000000000000000000000000000 */ neco = 0xffffffff; show_bit(neco); /* 11111111111111111111111111111111 */ neco = 20110512; show_bit(neco); /* 00000001001100101101110010110000 */
上記の例では配列として利用するために neco*5 という変数を宣言しています．
int型は先頭ビットが符号表現に当てられている*6ためunsigned int型を利用します．
なお今回の記事では前述のとおり32bit環境を想定しているため
配列で扱えるbool型は1つの配列（ビット列）に対して32個までとなる点に注意してください．
N番目の要素を操作する
それではいよいよビット列をbool型の配列として扱うための基本的な操作の説明に入ります．
/* #define N 7 */ unsigned neco = 20110512; show_bit(neco); /* 00000001001100101101110010110000 */ /* N番目の要素を取り出す */ printf("%dth bit is %d\n", N, neco>>N-1&1); /* 7th bit is 0 */ /* N番目の要素を1に */ neco |= 1<<N-1; show_bit(neco); /* 00000001001100101101110011110000 */ /* N番目の要素を0に */ neco &= ~(1<<N-1); show_bit(neco); /* 00000001001100101101110010110000 */ /* N番目の要素を反転 */ neco ^= 1<<N-1; show_bit(neco); /* 00000001001100101101110011110000 */
多くのビット演算と同様，ビットマスク*7を利用します．
N番目の要素を取り出す際は対象ビットが右端にくるようビット列をシフトさせ
数値の 1 をマスクとして利用し AND をとることで行います．
またN番目の要素を操作する際は数値の 1 を
シフト演算で N 番目まで移動させてマスクを作成し，
マスクとの OR や XOR 等をとることで行います．
なお上記のようにビット列を二進数で表記した場合，
通常の配列を表記する場合とは異なり右端から1番目，2番目，...と数えます．
頭の中でビット演算をイメージする際は注意してください．
2つの配列を比較する
次に2つの配列（ビット列）を比較する方法について説明します．
/* #define N 7 */ neco = 19880426; show_bit(neco); /* 00000001001011110101100111101010 */ nuco = 19900504; show_bit(nuco); /* 00000001001011111010100001011000 */ /* 2つの配列（ビット列）を比較 */ printf("neco == nuco : %d\n", neco==nuco); /* neco == nuco : 0 */ /* 2つの配列（ビット列）のN番目を比較 */ printf("neco[%d] == nuco[%d] : %d\n", N-1, N-1, (~((neco^nuco)>>N-1))&1); /* neco[6] == nuco[6] : 1 */
通常の配列と異なり，配列（ビット列）の全ての要素が等しいかどうかの比較は
数値を比較する際と同様に行なうことができます．
これは配列にunsigned int型を利用していることを考えれば自明*8です．
また2つの配列（ビット列）のN番目が等しいかどうかは，それぞれの XOR をとり
前述の「N番目の要素を取り出す」方法と組み合わせることで行っています．
まとめ
というわけで今回はビット演算によりint型をbool型の配列として扱う方法を紹介しました．
わかりやすさを重視するために配列（ビット列）の操作をコード内に直接書いていますが
実際に使用する場合はマクロ関数等でまとめてやると良いかもしれません．
ただしビット演算は可読性を下げるおそれがある上に要素数は32個が上限です．
プログラムの仕様や速度，メモリ量と相談して使うことをおすすめします．
なお今回の記事は[twitter:@necocen]がiPhoneアプリを作成した際に用いていた手法を
うろ覚えで インスパイア 参考にして勝手に解説しています．
今後も彼が周囲を感化することを期待してやみません*9．
*1:タグに「necocen」と付けたかったからではないです．多分．
*2:C++ではより便利な bitset という標準C++ライブラリの使用をオススメします．Programming Place PlusやC/C++ リファレンスを参照．
*3:wikipedia:ビット演算や初心者のためのポイント学習Ｃ言語がわかりやすいです
*4:記事に載せたコードだけで内容は理解できるはずですが，プログラムの全体像をイメージしたい場合は参照してください．
*5:この記事は[twitter:@necocen]をリスペクトしています
*6:wikipedia:符号付数値表現やWebで学ぶ 情報処理概論を参照
*8:法学では「社会通念上相当」とかいう曲がりくねった奇妙な表現を用います
