論理演算とビット演算

1.論理演算

論理表現は,ある条件が成り立つかどうか,ということを表すためのものであり, 真(成り立つ:1)と偽(成り立たない:0)の2値で表される.

例えば,「今日は6月である」は,真であるので,1となる.同様に, 「今日は木曜日である」は,真ではないので,0となる. このような,成り立つか成り立たないか,ということを二つの条件に対して 考慮するのが論理演算である. 例えば,「今日は6月で,水曜日である」は,「今日は6月である」が真で, かつ「今日は水曜日である」が真の場合に成り立つ(真となる).

これをベン図(Venn Diagram)で表すと,以下のようになる.

ベン図
左側の円が,「今日は6月である」を満たす日々の集合であり, 右側が「今日は水曜日である」を満たす日々の集合である. この両方が重なった部分が,「今日は6月で,水曜日である」を満たす日々となり, 円の外側が「今日は6月でもなく,水曜日でもない」日々ということになる. また,二つの円を併せた部分は,「今日は6月か,水曜日である」日々になる.

このように,二つの条件があったときに,その両方を満たす部分を,AND 条件を満たす,という.例えば,上記の例で,「今日は6月である」と「今日は 水曜日である」の AND条件を満たすのは,両方の円が重なった部分である.

これを,C言語では,

(今日は6月である) && (今日は水曜日である)

のように表す.

同様にどちらかの条件を満たす(上記の二つの円全体)部分を, OR条件を満たす,という.上記の例で,「今日は6月である」と「今日は水曜日である」の OR条件を満たすのは,二つの円全部である.

これは,

(今日は6月である) || (今日は水曜日である)

のように表す.

このような表現は,C言語のif文などで非常によく用いられる手法である. 例えば,ある変数xが2の倍数であり,かつ3の倍数であるかどうか を調べるif文は,

  if ( x % 2 == 0 && x % 3 == 0 ){        if ( x % 2 == 0 ){
        …                                    if ( x % 3 == 0 ){
  }                                                …
                                              }
                                          }
のように表記する.同様に, ある変数xが2の倍数か,または3の倍数の場合にのみ, 特定の処理を行いたい場合には,
  if ( x % 2 == 0 || x % 3 == 0 ){        if( x % 2 == 0 ){
     …                                       …
  }                                       } else if( x % 3 == 0 ){
                                              …
                                          }
のように記述する.

ここで,元に戻って真が1,真でない(偽の)場合が0であることを考えると, AND条件は,ひとつでも偽(0)があれば偽(0)となる.

これは数学の乗算と非常に似ている.そこで,この AND演算を 論理積 と呼ぶ.

実際,先ほどのif文は,&&を乗算に置き換えても正常に実行される.

 if ( (x % 2 == 0) * (x % 3 == 0) ){
次に,OR条件は,一つでも真があれば,他がすべて偽であっても,結果は 真となる.これは数学の加算に非常に似ている.そこで,このOR演算を 論理和と呼ぶ.ここでは省略するが,OR演算は加算に置き換えても 正常に実行される(0以外はすべて真と解釈される).

2.ビット演算

上記の論理演算を,数に適用したものがビット演算である.

ビット演算を行う場合,数値は2進数表記にして考えるとわかりやすい. 2進数では,各桁の数字は,それぞれ0が1という2種類の値をとる. これを上記論理演算の偽,真に対応させる. この上で,同じ桁位置の値について,上記の論理演算を適用する.

例えば,00101101bと 10010110bの AND演算,OR演算は以下のようになる.

    0 0 1 0 1 1 0 1 (32+8+4+1=45)        0 0 1 0 1 1 0 1
AND 1 0 0 1 0 1 1 0 (128+16+4+2=150)  OR 1 0 0 1 0 1 1 0
──────────                    ──────────     
    0 0 0 0 0 1 0 0 (4)                  1 0 1 1 1 1 1 1 (128+32+16+8+4+2+1=191)
C言語ではこのビット演算の ANDを,&で表記し,ORを|で表記する.

このビット演算は,一つの数値に複数の情報を持たせる時に非常に有用な手段と なる.例えば,8bitの数値の左のビットから順に演習第1回から第8回目ま での出席状況を,0は欠席,1は出席として表すと,

   0 1 1 0 1 1 1 0 b 
は,第1回,4回,8回のみ欠席していることを表す.

また,第5回が出席かどうか調べるためには,

   0 0 0 0 1 0 0 0 b (0x08)

と ANDをとって,その結果が0であるかそうでないか,
を調べれば良い.実際のプログラムは下記のようになる.

     int i, shusseki[130];
     /* 出席状況をshussekiに設定 */
     for(i = 0; i < 130; i++){
         if((shusseki[i] & 0x08) != 0) printf("出席\n");
         else printf("欠席\n");
     }
同様に,第6回のデータを出席にするには,
   0 0 0 0 0 1 0 0 b (0x04)
と ORをとってあげれば良い(確認せよ). 先週のプログラムで用いた,S_IFDIRとの AND演算は,このような演算によって, さまざまな情報の格納された st_modeという変数から, ディレクトリであるかどうかを表す1ビットのデータを取り出す処理を 行っていたのである.

このように,ある状態であるか,そうでないかを表すビットのことをフラグと 呼ぶ.これはC言語でもそれ以外でも非常によく使われる手法である. 2進数ではないが,例えば学生番号は先頭2桁が入学年度を表し,次の2桁が学科 を表している.これも同じような手法である.