排他的論理和（XOR）の性質とは？

排他的論理和（XOR）の性質の意味

入力が異なるときだけ1になる演算。A XOR A＝0、A XOR 0＝A が成り立ち、2回適用すると元に戻る可逆性を持つ。応用情報では、パリティ生成、RAID5のパリティ復元、ストリーム暗号の原理として問われる。

排他的論理和（XOR）の性質の具体例

RAID5ではディスクが1台壊れても、残りのデータブロック全てのXORで失われたブロックを復元できる。またA XOR K を同じ鍵Kで再度XORすると平文に戻るため、ワンタイムパッドの基礎になっている。

排他的論理和（XOR）の性質は試験でどう引っ掛けられる？

可逆だからこそ「XORしたから安全」ではない。同じ鍵を使い回すと2つの暗号文のXORから鍵が消え、平文どうしの関係が露出する。ORと違い、両方が1のときは0になる点も取り違えやすい。

排他的論理和（XOR）の性質と関連する用語

• ビット演算によるマスク処理
• 誤り検出・訂正符号

排他的論理和（XOR）の性質が出た過去問

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

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

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

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

  出典：平成28年度 春期 基本情報技術者試験 午前 問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）

• 負数を2の補数で表すとき、8ビットの2進正数nに対し-nを求める式はどれか。ここで、＋は加算を表し、ORはビットごとの論理和、XORはビットごとの排他的論理和を…

  正解：(n XOR 11111111) + 00000001

  要点：2の補数は全ビット反転＋1。反転はオール1とのXOR

  2の補数は「全ビットを反転してから1を加える」手順で求める。全ビット反転は、すべてのビットが1の値（8ビットなら11111111）との排他的論理和で実現できる。したがって n を反転したうえで 00000001 を加える式が -n を表す。論理和では特定ビットを1に固定するだけで反転はできない。

  出典：令和4年度 s 基本情報技術者試験 kamokuA 問1（IPA）