排他的論理和とは？

排他的論理和の意味

2つの入力が異なるときだけ1、同じときは0になる論理演算。XORまたはEORと書く。同じ値を2回XORすると元に戻る性質があり、簡易な暗号化、ビットの反転、パリティの計算、RAID5のパリティ生成など幅広く応用される。

排他的論理和の具体例

1010 XOR 0110 = 1100。データDと鍵KでD XOR K = C とすると、C XOR K = D で元に戻る。またA XOR A = 0、A XOR 0 = A が成り立つので、変数の値を作業領域なしで交換する技法にも使われる。

排他的論理和は試験でどう引っ掛けられる？

論理和（OR）は両方1のときも1だが、XORは両方1なら0になる。この1行の違いが真理値表の穴埋めでよく問われる。「排他的」という語からORの一種と早合点しないこと。

排他的論理和と関連する用語

• ド・モルガンの法則
• カルノー図
• 有限オートマトン

排他的論理和が出た過去問

• 図の論理回路と等価な回路はどれか。

  正解：AとBを入力とするXOR回路（Y出力）

  要点：NAND4個の定番構成は排他的論理和（XOR）と等価

  この回路は4個のNAND素子でできた定番の構成である。まず両入力のNAND出力をNとし、上側でAとN、下側でNとBのNANDをとり、その二つをさらにNANDで結んでいる。真理値表を作ると、AとBが同じ値のときは出力が0、異なるときだけ1になり、排他的論理和と一致する。

  出典：平成28年度 春期 基本情報技術者試験 午前 問23（IPA）

• 図に示すディジタル回路と等価な論理式はどれか。ここで、論理式中の“・”は論理積を、“＋”は論理和を、Xの上線はXの否定を表す。

  正解：X = A・(Bの否定) + (Aの否定)・B

  要点：NAND出力を各入力とANDしてORすると排他的論理和になる

  図の回路はまずAとBそれぞれの否定を論理和しており、これはAとBの論理積の否定（NAND）に等しい。その出力をAと論理積すればAかつBでない項、Bと論理積すればBかつAでない項が得られ、最後にこれらを論理和している。結果としてAとBが異なるときだけ1になる排他的論理和が構成される。

  出典：平成29年度 秋期 基本情報技術者試験 午前 問23（IPA）

• 図に示す，1桁の2進数xとyを加算して，z（和の1桁目）及びc（桁上げ）を出力する半加算器において，AとBの素子の組合せとして，適切なものはどれか。

  正解：A:排他的論理和／B:論理積

  要点：半加算器は和＝XOR、桁上げ＝ANDで構成する

  半加算器は2つの1桁の2進数を足し、和の1桁目zと桁上げcを出力します。zは入力が異なるときだけ1になるので排他的論理和、cは両方が1のときだけ1になるので論理積で実現できます。全加算器はこの半加算器2個と論理和1個で構成されます。

  出典：平成29年度 春期 基本情報技術者試験 午前 問22（IPA）

• 次に示す手順は，列中の少なくとも一つは1であるビット列が与えられたとき，最も右にある1を残し，他のビットを全て0にするアルゴリズムである。例えば，0010100…

  正解：論理積（AND）

  要点：A AND (A XOR (A-1)) で最下位の1ビットだけを抽出できる

  1を引くと最右の1が0になり、その右側の0が全て1へ変わる。元の値との排他的論理和は最右の1とその右側だけが1のマスクになるため、これと元の値の論理積を取ると最右の1だけが残る。例では00101000と00001111の論理積で00001000となる。

  出典：平成30年度 秋期 基本情報技術者試験 午前 問2（IPA）

• 8ビットの値の全ビットを反転する操作はどれか。

  正解：16進表記FFのビット列と排他的論理和をとる。

  要点：全ビット反転はFFとの排他的論理和（XOR）で行う

  排他的論理和は、片方のビットが1のとき相手のビットを反転させ、0のときはそのまま残す性質をもつ。全ビットが1である16進のFF（2進で11111111）とXORをとれば、8ビットすべてが反転する。論理和は1を作る方向にしか働かず、0とのORは元の値のままなので反転には使えない。

  出典：令和1年度 秋期 基本情報技術者試験 午前 問2（IPA）