平成30年度 秋期 午前 問2
離散数学
排他的論理和に関する問題
次に示す手順は，列中の少なくとも一つは1であるビット列が与えられたとき，最も右にある1を残し，他のビットを全て0にするアルゴリズムである。例えば，00101000 が与えられたとき，00001000 が求まる。aに入る論理演算はどれか。
手順1 与えられたビット列 A を符号なしの2進数と見なし，A から1を引き，結果を B とする。 手順2 A と B の排他的論理和（XOR）を求め，結果を C とする。 手順3 A と C の a を求め，結果を A とする。
- ア排他的論理和（XOR）
- イ否定論理積（NAND）
- ウ論理積（AND）
- エ論理和（OR）
答えと解説を見る
✓ これが正解ウ論理積（AND）
解説
1を引いた値と重ね合わせると、右端にある1だけが残ります。
符号なしの2進数から1を引くと、右端にある1は0に変わり、その右側にあった0はすべて1に変わります。元の値とこの値で排他的論理和を取ると、変化した範囲だけが1として浮かび上がります。00101000 なら、1を引いて 00100111 になり、排他的論理和は 00001111 です。浮かび上がった範囲は、右端の1とその右側をあわせた並びになっています。ここで元の値と論理積を取ると、両方が1である位置だけが残ります。右側は元の値が0なので消え、右端の1だけが生き残って 00001000 が得られます。どちらか一方にしか1が無い位置を落とす働きが、ここでは効いています。引き算で起きる繰り下がりの範囲が、そのまま取り出したい位置を指し示しているわけです。集合をビットで表す処理でよく使われる形です。
ほかの選択肢はなぜ違うのか
- ア排他的論理和（XOR）：排他的論理和を選ぶと、両方が1の位置が0に変わります。残したい右端の1がちょうど両方で1なので、その位置が消えてしまいます。手元の例では 00100111 となり、右端の1が消えたうえに、その右側が1で埋まってしまいます。
- イ否定論理積（NAND）：否定論理積は結果を反転させるので、もともと0だった上位のビットがすべて1に変わります。8ビットのうち大半が1で埋まり、他を0にするという求められた形から遠ざかります。反転をともなう演算は、絞り込みの用途には向きません。
- エ論理和（OR）：論理和はどちらかが1であれば1を返すので、1の個数が減ることはありません。手元の例では 00101111 となり、消したいはずの上位の1も右側の1も残ります。絞り込むには、共通する位置だけを取り出す働きのほうが必要です。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
- OR数学の手法を使って、いくつかの案から最も有利なものを選ぶ考え方です。期待される費用や利益を計算して比べるときに使います。
出典：平成30年度 秋期 基本情報技術者試験 午前 問2
同じ用語が出る問題
- 令和7年度 科目A 問6：SQLに関する問題（OR）
- 令和6年度 科目A 問1：X□Yの真理値表（OR）
- 平成31年度 春期 午前 問18：理想的なハッシュ法の説明（アルゴリズム）
- 平成29年度 春期 午前 問79（アルゴリズム）
- 平成29年度 春期 午前 問19：LRUに関する問題（アルゴリズム）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）