問1 午前 平成27年度 春期 基本情報技術者試験

問題

次に示す手順は、列中の少なくとも一つは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)

解説

実際に手順を踏んで試してみると解きやすいです。アルゴリズムとは問題を解くための「手順」や「手続き」くらいの意味で捉えておけばOKです。

例として「00101000が与えられたとき、00001000が求まる」と書いてあるので、実際にこれを使って手順1~手順3を見てみましょう。

まず手順1。Aから1を引き、とあるので、1を引きます。A「00101000」から1を引くと、B「00100111」になります。右側の1000が0111になってるところが引き算です。これをBとします。

手順2では、AとBの排他的論理和を求め、とあります。排他的論理和とは1+1=0,1+0=1,0+0=0の演算です。1と0だったら1になって、1同士だったら0に、0同士でも0になります。

まずAの一番左をみると0です。Bの一番左も0です。だから一番左は0になります。これを続けていくと、C「00001111」になります。

さて最後の手順3ですが、欲しい答えは「00001000」だということを頭に入れておきます。A「00101000」とC「00001111」を眺めて、どうやったら「00001000」が作れるか考えます。とりあえず全選択肢を試してみましょう。

アは排他的論理和ですから、 00100111になります。これは欲しい結果ではありません。

イ の否定論理積(NAND)は、ANDを取ってから否定をとるものです。とりあえずANDをとってみると、00001000となります。これを否定すると、 否定とはビットの反転なので、1は0、0は1にします。すると11110111になります。これは欲しい結果ではないのでこの選択肢は誤りです。

ウの論理積はイの前半でやったことです。0×1は0、1×1は1ですから、00001000になります。これが正解です。

エ の論理和は足し算です。1+1=1、1+0=1です。1+1が1ということに注意してください。排他的論理和では1+1=0です。論理和と排他的論理和は 「1+1の結果だけ」が異なります。エでは論理和なので1+1は1として考えると、00101111になります。これは欲しい結果ではないので誤りです。

よってウが正解です。

ちなみにこのアルゴリズムを暗記して対策しようとしないようにしましょう。このようなアルゴリズムは無限にあります。いちいち覚えて対処できるものではありません。その場で計算して導けるようにしましょう。

解答