問題プレビューID: f31752c1基本情報技術者試験 午前免除試験 2020年1月26日

問 2
基本情報技術者試験 午前免除試験 2020年1月26日

次に示す手順は,列中の少なくとも一つは 1 であるビット列が与えられたとき,最も右にある 1 を残し,他のビットを全て 0 にするアルゴリズムである。例えば,00101000 が与えられたとき,00001000 が求まる。a に入る論理演算はどれか。

手順 1 与えられたビット列 AA を符号なしの 2 進数と見なし,AA から 1 を引き,結果を BB とする。 手順 2 AA と BB の排他的論理和(XOR)を求め,結果を CC とする。 手順 3 AA と CC の   a   を求め,結果を AA とする。

解説

正解は「ウ」である。

A=00101000A=00101000(10 進数で 40)のとき,B=A−1=00100111B=A-1=00100111(39)である。AA と BB の排他的論理和を求めると C=00001111C=00001111 となる。ここで AA と CC の論理積(AND)を求めると 00101000∧00001111=0000100000101000 \land 00001111 = 00001000 となり,最も右にある 1 だけが残り,他のビットは全て 0 になる。

AA から 1 を引くと,最も右にある 1 が 0 に変わり,それより下位のビットが全て 1 になる。このとき XOR をとると,変化した部分(最下位の 1 とそれより下位のビット)だけが 1 になる。そこで元の AA との AND をとれば,最も右にある 1 だけを抽出できる。

  • ア: XOR では CC がそのまま残り,他のビットも 1 になってしまう。
  • イ: NAND では求めるビット列にはならない。
  • エ: OR では CC の 1 の部分が加わり,他のビットが 1 になってしまう。

関連問題

本文が同じ・似ている問題を表示しています