平成30年度 秋期 基本情報技術者試験 午前 問2
テクノロジ／アルゴリズム次に示す手順は，列中の少なくとも一つは1であるビット列が与えられたとき，最も右にある1を残し，他のビットを全て0にするアルゴリズムである。例えば，00101000が与えられたとき，00001000が求まる。aに入る論理演算はどれか。 手順1 与えられたビット列Aを符号なしの2進数と見なし，Aから1を引き，結果をBとする。 手順2 AとBの排他的論理和（XOR）を求め，結果をCとする。 手順3 AとCの a を求め，結果をAとする。
出典：平成30年度 秋期 基本情報技術者試験 午前 問2
- ア排他的論理和（XOR）
- イ否定論理積（NAND）
- ウ論理積（AND）
- エ論理和（OR）
正解：ウ
解説
この手順は，2の補数表現の性質を利用して最も右にある1だけを残すアルゴリズムです。Aから1を引くと，最も右にある1のビットが0になり，それより下位のビットは全て1に反転します。AとBのXORをとると，最も右の1のビットからそれより下位のビットまでが全て1になり，それより上位のビットは0になります（Cの値）。最後にAとCの論理積（AND）を取ると，Cが1である範囲のうちAでも1になっているビットは元々の最も右の1のビットだけなので，それ以外は全て0になり，求める結果が得られます。
選択肢ごとの解説
- ア誤り。AとCの排他的論理和を取ると，Cの範囲のビットがすべて反転してしまい，最も右の1だけを残すことができません。
- イ誤り。否定論理積では出力のほとんどが1になってしまい，目的のビットパターンは得られません。
- ウ正しい。AとCの論理積を取ると，最も右にある1のビットだけが残り，他のビットは全て0になります。
- エ誤り。論理和を取ると，Cが1であるビット（最も右の1から下位ビット全て）がそのまま1として残ってしまい，1つのビットだけを残すことができません。