平成27年度 春期 午前 問1
離散数学
排他的論理和に関する問題
次に示す手順は，列中の少なくとも一つは 1 であるビット列が与えられたとき，最も右にある 1 を残し，他のビットを全て 0 にするアルゴリズムである。例えば，00101000 が与えられたとき，00001000 が求まる。a に入る論理演算はどれか。
手順1 与えられたビット列 A を符号なしの 2 進数と見なし，A から 1 を引き，結果を B とする。 手順2 A と B の排他的論理和（XOR）を求め，結果を C とする。 手順3 A と C の ［ a ］ を求め，結果を A とする。
原典の手順3 の a は罫線で囲んだ空欄です。本ファイルでは ［ a ］ と書きました。
- ア排他的論理和（XOR）
- イ否定論理積（NAND）
- ウ論理積（AND）
- エ論理和（OR）
答えと解説を見る
✓ これが正解ウ論理積（AND）
解説
A と C の共通部分を取ると最も右の1だけが残ります。
手順1 で A から 1 を引くと、最も右にある 1 より下の桁が全て 1 に変わり、その 1 自身は 0 になります。それより上の桁は変わりません。手順2 で A と B の排他的論理和を取ると、変化した桁だけが 1 として並ぶので、C は最も右の 1 とそこから下の桁が全て 1 のビット列になります。判定の軸は、この C と元の A を重ねたときに何が残るかという一点です。両方に 1 が立っている桁だけを残す論理積を使えば、C で 1 になっている範囲のうち A でも 1 だった桁、つまり最も右にある 1 だけが残り、他の桁は 0 になります。設問の例で確かめると、A が 00101000、B が 00100111、C が 00001111 で、両方に 1 が立つ桁は右から 4 番目だけなので 00001000 が得られます。
ほかの選択肢はなぜ違うのか
- ア排他的論理和（XOR）：二つのビット列で 1 の立ち方が違う桁だけを残す演算です。例の値で計算すると 00100111 となり、手順1 で作った B に戻ってしまうので、1 ビットだけの形になりません。
- イ否定論理積（NAND）：両方に 1 が立つ桁を 0 に、それ以外を 1 に置き換える演算です。例の値では 11110111 となり、0 にしたいはずの上の桁がほとんど 1 で埋まってしまいます。
- エ論理和（OR）：どちらか一方でも 1 が立っていれば 1 とする演算です。例の値では 00101111 となり、元からあった 1 も新しく立った 1 も全て残るため、右端の一つに絞れません。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
- OR数学の手法を使って、いくつかの案から最も有利なものを選ぶ考え方です。期待される費用や利益を計算して比べるときに使います。
出典：平成27年度 春期 基本情報技術者試験 午前 問1
同じ用語が出る問題
- 令和7年度 科目A 問6：SQLに関する問題（OR）
- 令和6年度 科目A 問1：X□Yの真理値表（OR）
- 平成31年度 春期 午前 問18：理想的なハッシュ法の説明（アルゴリズム）
- 平成29年度 春期 午前 問79（アルゴリズム）
- 平成29年度 春期 午前 問19：LRUに関する問題（アルゴリズム）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）