論理演算(Logical Operation)
別名ブール演算(Boolean Operation)とも呼ばれ、0(偽) もしくは 1(真)か0(偽) を求める演算になります。
演算の種類としては、AND,OR,NAND,NOR,XOR の5種類があります。
論理積(AND)
X AND Y としたとき、X かつ Y となります。
つまり1(真)と0(偽)で表す場合、XとYがどちらか1(真)のときに1(真)となり、それ以外は0(偽)となります。
X AND Y
1 * 1 = 1
0 * 1 = 0
1 * 0 = 0
0 * 0 = 0
上記のように、両方の積によって1(真)0(偽)を求めることができることから、ANDは論理積といいます。
論理和(OR)
X OR Y としたとき、X または Y となります。
つまり1(真)と0(偽)で表す場合、XとYのどちらかでも1(真)であれば1(真)となり、両方0(偽)のときは0(偽)となります。
X OR Y
1 + 1 = 1
0 + 1 = 1
1 + 0 = 1
0 + 0 = 0
上記のように、両方の和によって1(真)0(偽)を求めることができることから、ANDは論理積といいます。
否定論理積(NAND)
NAND = Not AND
つまり、論理積ではないという意味なになります。
X NAND Y としたとき、X かつ Y ではない となります。
つまり1(真)と0(偽)で表す場合、すべての入力値が1(真)の場合に0(偽)を出力し、それ以外の場合には1(真)なります。
X AND Y Not
1 * 1 = 0
0 * 1 = 1
1 * 0 = 1
0 * 0 = 1
否定論理和(NOR)
NOR = Not OR
つまり、論理和ではないという意味なになります。
X OR Y としたとき、X または Y ではないとなります。
つまり1(真)と0(偽)で表す場合、すべての入力値が0(偽)の場合1(真)となり、それ以外の場合は0(偽)をとなります。
要するに、どちらかに1(真)があれば0(偽)にるということです。
X NOR Y Not
1 + 1 = 0
0 + 1 = 0
1 + 0 = 0
0 + 0 = 1
上記のように、両方の和によって1(真)0(偽)を求めることができることから、ANDは論理積といいます。
排他的論理和(XOR)
XOR = Exclusive OR
Exclusive(排他的) : 仲間でない者を退ける
入力値が異なるものを検出するということになり、仲間外がいたら1(真)となります。
X OR Y としたとき、X または Y となります。
つまり1(真)と0(偽)で表す場合、入力値が異なる場合に1(真)となり、入力値が同じときは0(偽)となります。
X OR Y
1 1 = 0
0 1 = 1
1 0 = 1
0 0 = 0
基本情報技術者試験の過去門
実際の過去問で解説したいと思います。
問題
次に示す手順は、列中の少なくとも一つは1であるビット列が与えられたとき、最も右にある1を残し、他のビットを全て0にするアルゴリズムがある。
例えば、00101000が与えられたとき、00001000が求まる。下記手順の a に入る論理演算は何か。
手順1
与えられらビット列Aを符号なしの2進数と見なし、Aから1を引き、結果をBとする。
手順2
AとBの排他的論理和(XOR)を求め、結果をCとする。
手順3
AとCの a を求め、結果をAとする。
まずAの 00101000 から2進数での計算で1を引いてBを求めます。
00101000
- 1
=00100111
となり、Bは00100111となります。
この計算は2進数なので一の位で0-1となり、0が引けないので繰り上がり、次も０なので繰り上がり千の位でようやく１が引けて、引けなかった0が1になるというものです。
※説明が下手で分かりにくいと思いますので、別記事に2進数の計算を上げております。
https://qiita.com/hi-scorp-d/items/3e6c72dfb3c871f6559f
次にAとBの排他的論理和(XOR)でCを求めます。
A XOR B C
0 0 = 0
0 0 = 0
1 1 = 0
0 0 = 0
1 0 = 1
0 1 = 1
0 1 = 1
0 1 = 1
となり、Cは00001111となります。
最後に、AとCで求めたい数字00001000となる演算を考えます。
A ? C
0 0 = 0
0 0 = 0
1 0 = 0
0 0 = 0
1 1 = 1
0 1 = 0
0 1 = 0
0 1 = 0
となり、?が何かを考えます。
注目すべきは、中央の1と1のときは1で、それ以外は必ず0がどちらかにあり、その場合は0になっています。
この結果になるのは…
そう！ 積のときだけですよね！
A AND C
0 * 0 = 0
0 * 0 = 0
1 * 0 = 0
0 * 0 = 0
1 * 1 = 1
0 * 1 = 0
0 * 1 = 0
0 * 1 = 0
つまり a に当てはまる答えは、 論理積(AND) となります。