「XOR」は論理演算について説明しているこの項目へ転送されています。論理回路については「XORゲート」をご覧ください。
ベン図による排他的論理和 P ⊻ Q {\displaystyle P\veebar Q}
排他的論理和(はいたてきろんりわ、英: exclusive or / exclusive disjunction)とは、ブール論理や古典論理、ビット演算などにおいて、2つの入力のどちらか片方が真でもう片方が偽の時には結果が真となり、両方とも真あるいは両方とも偽の時は偽となる演算(論理演算)である。XOR、EOR、EX-OR(エクスオア、エックスオア、エクソア)などと略称される。 中置演算子のある体系では、中置演算子を利用した中置記法により表記されることが多い。演算子は ⊻ {\displaystyle \veebar } (Unicode: U+22BB ?)、 ∨ ˙ {\displaystyle {\dot {\vee }}} 。誤解のおそれがないときは、XOR、xor、 ⊕ {\displaystyle \oplus } (Unicode: U+2295 ?)、+、≠ なども使われる。 論理学などでは ⊻ {\displaystyle \veebar } を使用して P ⊻ Q {\displaystyle P\veebar Q} と書くことが多く、論理回路などでは ⊕ {\displaystyle \oplus } を使用して A ⊕ B {\displaystyle A\oplus B} と書くことが多い。 記号を使った中置演算子としては ^ や @ などが使われることが多く、キーワードが演算子になるような言語では XOR や xor などが使われることが多い。z = x ^ y;z = x xor y; 「私の身長は160cm以上である」と「私の体重は52kg未満である」の二つの命題の排他的論理和は、これらのうち一方のみが成り立つことであるから、「私は身長160cm以上であり体重が52kg以上である。あるいは、私は身長160cm未満であり体重が52kg未満である。」となる。 なお、2つの命題 A, B について共通部分 A ∧ B が空集合であれば、排他的論理和は論理和と同じになる。例えば A = 「私の身長は160cmである」と B = 「私の身長は170cmである」は同時に成立することはない(共通部分が空である)ので、(A xor B) は (A ∨ B) と同じく「私の身長は160cmまたは170cmのいずれか一方である」となる。「対称差」も参照 排他的論理和は、論理和、論理積、否定を用いて、 P ⊻ Q = ( P ∧ ¬ Q ) ∨ ( ¬ P ∧ Q ) {\displaystyle P\veebar Q=(P\land \lnot Q)\lor (\lnot P\land Q)} P ⊻ Q = ( P ∨ Q ) ∧ ( ¬ P ∨ ¬ Q ) {\displaystyle P\veebar Q=(P\lor Q)\land (\lnot P\lor \lnot Q)} P ⊻ Q = ( P ∨ Q ) ∧ ¬ ( P ∧ Q ) {\displaystyle P\veebar Q=(P\lor Q)\land \lnot (P\land Q)} などと表すことができる。 命題 P命題 QP ? Q 2を法とする剰余体 Z / 2 Z {\displaystyle \mathbb {Z} /2\mathbb {Z} } での加算(この体では加算と減算は等しい)は、0 を偽、1 を真とみなすと、排他的論理和となる。つまり、偶数 (0, 偽) どうしまたは奇数 (1, 真) どうしを加えると偶数 (0, 偽) になり、偶数 (0, 偽) と奇数 (1, 真) を加えると奇数 (1, 真) になる。 2進数表現した数値の各ビットに対し、0 を偽、1 を真とみなして排他的論理和を求めた結果を、ビットごとの排他的論理和、排他的ビット和、または単に排他的論理和と呼ぶ。 ?01 ビットごとの排他的論理和は、桁上がりを無視した2進数の加算の結果と等しい。つまり、ビットごとの排他的論理和は、2 の冪を位数とする有限体 G F ( 2 n ) {\displaystyle \mathrm {GF} (2^{n})} での加減算(この体では加算と減算は等しい)に等しい。(なお、2を法とする剰余体 Z / [ 2 ] {\displaystyle \mathbb {Z} /[2]} は、位数2の有限体 G F ( 2 ) {\displaystyle \mathrm {GF} (2)} である。) 1 桁の2進数の排他的論理和は、半加算器の一部である。 排他的論理和とビットごとの排他的論理和とは、異なることがある。0(偽)と 1(真)については、排他的論理和とビットごとの排他的論理和は等しい。しかし、0 でない値が全て真とみなされる環境や、0 でない値が真 (1) に暗黙の型変換される環境では、0 と 1 以外の値に対しても(ビットごとでない)排他的論理和を求めることができ、結果は一般にはビットごとの排他的論理和とは異なるので注意が必要である。 ビットごとの排他的論理和は、コンピュータ上でビット演算を行っている場合に、特定のビットだけを反転させるのによく用いられる。ある数値と、その数値のビットを反転させたい部分を 1 にした数値との排他的論理和をとると、指定した部分が反転した数値が得られる: 0011 ( 2 ) ⊕ 0110 ( 2 ) = 0101 ( 2 ) {\displaystyle 0011_{(2)}\oplus 0110_{(2)}=0101_{(2)}} 多くのプロセッサで、レジスタをゼロにする場合に、直接ゼロをレジスタへ転送するより、自分自身とのXORをとってゼロとするほうが有利な場合がある。 X ⊕ X = 0 {\displaystyle X\oplus X=0} 主に以下の条件が成立する場合、言語処理系が最適化の一環としてXORを用いる。 ビットごとの排他的論理和によって、多数の入力における偽の個数の奇数・偶数(パリティ)が検出できるので、誤り検出に用いられる。
表記法
プログラミング言語
例
性質
真理値表
真真偽
真偽真
偽真真
偽偽偽
ビットごとの排他的論理和
001
110
P = 0011 K = 0110 P ? K = 0101
ビット演算
即値のゼロを省略することにより、コードサイズが削減できる。
処理がレジスタとALUのみで完結するので、サイクル数や消費電力が削減できる。
XOR演算によるフラグ変化がその後の処理に不利な影響を残さない。
Size:17 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef