論理演算

真偽値（0と1）の上の演算を論理演算 (logical operations) またはブール演算 (boolean operations) と言う。つまり，論理積，論理和，否定，及びそれらの組み合わせでできる演算のことだ。

論理積 ∧，論理和 ∨，排他的論理和 ⊕，否定 ¬ はそれぞれ以下のように定義される。

0 ∧ 0 = 0	0 ∨ 0 = 0	0 ⊕ 0 = 0	¬ 0 = 1
0 ∧ 1 = 0	0 ∨ 1 = 1	0 ⊕ 1 = 1	¬ 1 = 0
1 ∧ 0 = 0	1 ∨ 0 = 1	1 ⊕ 0 = 1
1 ∧ 1 = 1	1 ∨ 1 = 1	1 ⊕ 1 = 0

この章では，レジスタや主記憶の中身を「2進法で表された数」ではなく「真偽値の並び」として扱う演算命令について学ぶ。そのような演算は，例えば以下のような場面で必要になる。

あるコンピュータに4つのスイッチ a, b, c, d が接続されており，それらが押下されているかどうかはそれぞれ，0xffbb 番地からの読み出しで得られる1バイトの値の第0〜3ビットに格納されている。このとき，スイッチ c が押下されているかどうか（第2ビットが1かどうか）を調べるにはどうしたらよいか?
ある動画像ファイル形式では，水平画素数 h（12ビット），垂直画素数 v（12ビット），画素の縦横比を表す符号 a（4ビット），フレームレートを表す符号 f（4ビット）を並べた32ビットの値を，定められた位置に含めなければならない。与えられた h, v, a, f からこの32ビットの値を得るにはどうしたらよいか?　逆に，32ビットの値から h, v, a, f を得るにはどうしたらよいか?
あるコンピュータのCPUには乗算命令がない。このコンピュータでなるべく効率よく乗算を行うにはどのようにプログラムすればよいか?

ビットごとの論理演算 (bitwise logical operations)

下記の演算 &, |, ^, ~ は，それぞれ「ビットごとの論理積，論理和，排他的論理和，否定」と呼ばれる（C言語やJavaではこれらの演算記号を用いる）。ビットごとの論理積，論理和，排他的論理和は，被演算数 a, b の第 i ビット同士の論理積，論理和，排他的論理和を並べたものだ。ビットごとの否定は，被演算数 a の各ビットを反転（0は1に，1は0にする）したものだ。

            a = 1011100101110101 (= 0xb975)
            b = 1111111100000000 (= 0xff00)
        とする。
bitwise-AND
        a & b = 1011100100000000 (= 0xb900)
bitwise-OR
        a | b = 1111111101110101 (= 0xff75)
bitwise-XOR
        a ^ b = 0100011001110101 (= 0x4675)
bitwise-NOT
          ~ a = 0100011010001010 (= 0x468a)

機械語命令 AND, OR, XOR, NOT は，それぞれ上記のビットごとの論理演算を表す。

    mov     ebx, 0xff0
    mov     eax, 0xb97531ca
    and     eax, 0xff00ff00   ; eaxの値は0xb9003100になる
    or      eax, ebx          ; eaxの値は0xb9003ff0になる
    xor     eax, 0xffff0000   ; eaxの値は0x46ff3ff0になる
    not     eax               ; eaxの値は0xb900c00fになる

AND, OR, XORは，ディスティネーションオペランドの一部のビットの値を変更したいときに使うことができる。

AND命令は，特定のビットを0にするために使える（下図(a)）。
OR命令は，特定のビットを1にするために使える（下図(b)）。
XOR命令は，特定のビットを反転するために使える（下図(d)）。

例:

and eax, 0xff00ff00 では，eaxの第0〜7ビット及び第16〜23ビットが0になり，それ以外のビットは変化しない。
or eax, 0xff0 では，eaxの第4〜11ビットが1になり，それ以外のビットは変化しない。
xor eax, 0xffff0000 では，eaxの第16〜31ビットが反転し，それ以外のビットは変化しない。

一部のビットを0または1にすることを，「そのビットをマスクする」と言う。また，0または1にしたいビットや反転したいビットを指定するためのビット列（上記の例の 0xff00ff00 や 0xff0 や 0xffff0000）のことを「ビットマスク」と言う（「レジスタXXの値はビットマスクを表す」のように言う）。

参考: 上図の(c)のように，OR命令は，複数のビット列を一つにまとめる（パックする）ことにも使える（ORではなくADDを使ってもよい）。

補足: TEST命令

TEST命令は，「ANDと同じ演算を行うが，結果をディスティネーションオペランドに代入しない」命令だ。CMP命令が「SUBと同じ演算を行うが，結果をディスティネーションオペランドに代入しない」のと類似している。CMPと同じく条件付きジャンプと組にして使うための命令であり，JZ または JNZ と組にして，「レジスタ（または主記憶内領域）の中のある1ビットが0かどうか（または複数のビットがすべて0かどうか）」を調べるのに使うことができる。

例えば，このページの冒頭で述べた「第2ビットが1かどうか調べる」ことは，以下のようにすれば行える。

    test    eax, 4      ; eaxの第2ビットを調べる
    jnz     pressed     ; eaxの第2ビットが1

4 は「第2ビットのみ1である数」だ。4 とのビットごとの論理積を求めると，EAX中の第2ビットのみ残り，それ以外のビットは0にマスクされる。従って，第2ビットが 0 なら演算結果全体も 0 になり，第2ビットが 1 なら演算結果は非0になる。また，AND命令ではなくTEST命令を使っているので，EAXの値は変更されない。

参考: xor eax, eax

問: xor eax, eax を実行すると，EAXの値はいくらになるか?

mov eax, 0 の代わりに xor eax, eax を使うことを好むプログラマもいる。機械語にすると，前者は b8 00 00 00 00 の5バイト，後者は 31 c0 の2バイトだ。

同じように，EAXの値が 0 か否か調べたいとき，cmp eax, 0 の代わりに test eax, eax を好むプログラマもいる（and eax, eax または or eax, eax でもよい）。機械語にすると，前者は 3d 00 00 00 00 の5バイト，後者は 85 c0 の2バイトだ（cmp eax, byte 0 と書けば 83 f8 00 の3バイト）。

シフト命令

SHL (shift logical left) は，ディスティネーションオペランド内の各ビットを左にずらす命令（左シフト命令）だ。つまり，実行前の第0ビットの値が第1ビットに，実行前の第1ビットの値が第2ビットに，…，実行前の第30ビットの値が第31ビットに代入される。実行前の最上位ビットの値はCFに代入される。実行後の第0ビットの値は0になる。

何ビットずらすかを第2オペランドで指定できる。

    mov     eax, 0xcb20     ;   = 1100101100100000
    shl     eax, 1          ;    11001011001000000 (=0x19640)になる
    shl     eax, 3          ; 11001011001000000000 (=0xcb200)になる

上の例のように，計4ビットシフトすると，16進数の1桁分シフトしたのと同じになる。

同様に，SHR (shift logical right) は，右にシフトする命令だ。

    mov     eax, 0xcb20     ; = 1100101100100000
    shr     eax, 1          ;    110010110010000 (=0x6590)になる
    shr     eax, 3          ;       110010110010 (= 0xcb2)になる

参考: SAR (shift arithmetic right) は，SHR とほとんど同じだが，「実行後の最上位ビットの値は実行前と同じ」である点だけが異なる。 SHR は，実行後の最上位ビットの値は0になる。
- 符号付き数を扱う場合，SAR を使うと，2で割ることと右シフトが一致する。次節の「シフト演算と乗除算」も参照。
参考: ROL (rotate left) は，SHL と同様に左シフトを行うが，実行前の最上位ビットの値を第0ビットに代入する（左端の値を右端に移動する）。このような命令を巡回シフト命令（またはローテート命令）と言う。右巡回シフトを行う ROR (rotate right) もある。
- RCL (rotate left with carry) は，ROL と同様だが，実行前の最上位ビットの値をCFに代入し，実行前のCFの値を第0ビットに代入する（CFも含めて巡回シフトする）。逆方向に巡回シフトする RCR (rotate right with carry) もある。

シフト演算と乗除算

シフト演算やビットマスク演算は，以下のように2進数に対する乗除算として解釈することができる。

左に k ビットだけシフトすることは，2^k 倍することと等しい（例えば3ビット左にシフトすることは8倍することと等しい）。
```
0001111110100101 = 0x1fa5 =  8101
1111110100101000 = 0xfd28 = 64808
```
右に k ビットだけシフトすることは，2^k で割ることと等しい（ただし小数点以下は切り捨て）（例えば3ビット右にシフトすることは8で割ることと等しい）。
```
0001111110100101 = 0x1fa5 = 8101
0000001111110100 =  0x3f4 = 1012
```
下位 k ビットだけ残し，それ以外のビット（上位 32 − k ビット）を0にすることは，2^k で割った余りを計算しているのと等しい（例えば，下位3ビットだけ残すことは，8で割った余りを計算しているのと等しい）。
```
0001111110100101 = 0x1fa5 = 8101
0000000000000101 =    0x5 =    5
```

「2^k 倍する」「2^k で割る」などは乗除算命令を使うよりシフト命令を使った方が簡単だ。どのレジスタに対しても実行できるし，処理時間も短い。

同様に，「2^k で割った余りを求める」ことはビットマスク演算で行える。一例として，例えば「偶数か奇数か調べる」ことは「2で割った余りが 0 か 1 か調べる」ことと同じなので，TEST命令で最下位ビットが 0 か 1 か調べるだけでできる。

シフトと加算による乗算

小学校で習った10進法の筆算について考えよう。 34567 × 123 は以下のように計算できる。

   34567
x)   123
---------
  103701  ← 被乗数 × 乗数の第0桁
  69134   ← 被乗数 × 乗数の第1桁
 34567    ← 被乗数 × 乗数の第2桁
---------
 4251741  ← 上記の積の和

つまり，123 = 100 + 20 + 3 なので，被乗数の3倍と20倍と100倍を求めて和を計算すればよい，というわけだ。

2進法でも同じことだ。被乗数と乗数の1桁との積を求めてすべて合計すればよい。下記は，0xa7 (= 167) と 0x16 (= 22) の積を計算している。結果は 0xe5a (= 3674) だ。

    10100111
x)     10110
-------------
           0  ← 被乗数 × 乗数の第0桁
   10100111   ← 被乗数 × 乗数の第1桁
  10100111    ← 被乗数 × 乗数の第2桁
        0     ← 被乗数 × 乗数の第3桁
10100111      ← 被乗数 × 乗数の第4桁
-------------
111001011010  ← 上記の積の和

2進法では「乗数の1桁」は0か1なので，「乗数の第 i ビットが1ならば，被乗数を i ビット左シフトしたものを結果に加える」というアルゴリズムで乗算を行える。

乗算命令がなくても上記の方法で乗算を行うことができる。定数倍する場合は，ループを使わなくても以下のように記述できる。

    ; eaxの値を10倍する
    mov     ebx, eax
    shl     eax, 2      ; 元の4倍
    add     eax, ebx    ; 元の5倍
    shl     eax, 1      ; 元の10倍

    ; eaxの値を100倍する
    mov     ebx, eax
    shl     eax, 1      ; 元の2倍
    add     eax, ebx    ; 元の3倍
    shl     eax, 3      ; 元の24倍
    add     eax, ebx    ; 元の25倍
    shl     eax, 2      ; 元の100倍

7. 論理演算