出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
8ビット列A, Bに対して、排他的論理和(XOR)と論理積(AND)の性質を用いて、C=(((A⊕B)⊕B)⊕A)・Aという演算結果を求める問題。ビット演算の性質(自己逆元性、べき等性)の理解が必要。
8ビット列A=01011101, B=10101101について、C=(((A⊕B)⊕B)⊕A)・Aという演算で得られるビット列Cを求める問題。
① 同じものを2回⊕すると消える(X⊕X=0、X⊕0=X)。0との論理積は0
② (A⊕B)⊕B=A → A⊕A=00000000 → 00000000・A=00000000
③ 00000000(①)
排他的論理和(XOR)には、同じ値を2回XORすると元に戻る性質(X⊕Y⊕Y=X)がある。これを式に当てはめると、(A⊕B)⊕B=A(BでXORした結果に再びBをXORすると元のAに戻る)。次にこの結果にAをXORすると、A⊕A=0(同じビット列同士のXORは全て0になる)となり、ここまでの計算結果は全て0のビット列(00000000)になる。最後にこの結果とAとの論理積(AND)を取るが、0とのANDは常に0になるため、Cは全て0のビット列00000000となる。したがって①が正しい。
■ 1ビットの排他的論理和(⊕)と論理積(・)
・⊕: 2つが同じなら0、違えば1(0⊕0=0、0⊕1=1、1⊕0=1、1⊕1=0)
・・: 両方1のときだけ1、それ以外は0
ビット列どうしの演算は、同じ位置のビットごとにこれを行います。
■ 「同じものを2回⊕すると元に戻る」理由
上の表から、どんなビットXでもX⊕X=0、X⊕0=Xです。また⊕は計算する順番(かっこの位置)を変えても結果が同じなので、(A⊕B)⊕B=A⊕(B⊕B)=A⊕0=Aとなります。
排他的論理和(XOR)には、同じ値を2回XORすると打ち消し合って元の値に戻る(X⊕Y⊕Y=X)という重要な性質があり、これを利用すると複雑に見えるXORの式を簡略化できる。さらに0との論理積(AND)は常に0になるという性質も合わせて使うと、この問題を暗算に近い形で解ける。
キーワード: 排他的論理和、論理積、ビット演算、情報・論理