最も右の1だけを残すビット演算と、A−1とXORの役割
基本情報技術者試験 平成30年度秋期 午前 問2 ／ 基礎理論 › 離散数学
過去問にチャレンジ
次に示す手順は，列中の少なくとも一つは1であるビット列が与えられたとき，最も右にある1を残し，他のビットを全て0にするアルゴリズムである。例えば,00101000が与えられたとき,00001000が求まる。aに入る論理演算はどれか。 手順1与えられたビット列Aを符号なしの2進数と見なし，Aから1を引き，結果をBとする。手順2AとBの排他的論理和(XOR)を求め，結果をCとする。手順3AとCのaを求め，結果をAとする。
- ア
排他的論理和(XOR)
- イ
否定論理積(NAND)
- ウ
論理積(AND)
- エ
論理和(OR)
会話形式の解説
講師今回は、ビット列から最も右にある1だけを取り出すアルゴリズムの問題です。手順の最後で使う演算を選びますが、まず押さえたいのは、1を引いたときにビット列がどう変わるかです。
受験者引き算をビットで考えるのが苦手です。00101000から1を引くと、どうなるのでしょうか。
講師右端から見ていくと、下の桁が0なので借りが続き、最も右の1まで上がっていきます。結果として、最も右の1が0になり、その右側の0はすべて1になります。例ではBが00100111です。
受験者変わるのは最も右の1から右端までで、それより左はAと同じなのですね。
講師そのとおりです。では、AとBのXOR（排他的論理和、ビットが異なる桁だけ1にする演算）であるCはどうなりますか。
受験者変わった範囲だけが1になるので、Cは00001111です。最も右の1の位置から右端までが1になっています。
講師このCは、範囲を指定するマスクの役目をします。あとはAとCを組み合わせて00001000になる演算を探します。まずXORで組み合わせるとどうでしょう。
受験者00101000と00001111のXORは00100111です。これはBと同じ値ですね。
講師CはAとBのXORなので、もう一度AとXORを取るとBに戻ります。だからXORでは目的を果たせません。OR（論理和）ならどうなりますか。
受験者どちらかが1なら1なので00101111です。Aの上位の1もCの右側の1も残ってしまい、1が一つになりません。
講師では、AND（論理積、両方が1の桁だけ1にする演算）を考えてみましょう。Cが1の範囲のうち、Aが1なのはどの桁でしょうか。
受験者最も右の1の桁だけです。その右側はAが0なので、結果は00001000になり、例と一致します。
受験者NAND（否定論理積）も候補に見えましたが、ANDの結果を反転するので11110111になり、0と1が逆になってしまうのですね。
講師はい。NANDのように名前にANDが入っている選択肢は、反転の有無で引っかけになりやすいところです。もう一つ補足すると、負の数を2の補数で表す場合は、A AND (−A) でも同じように最も右の1を取り出せます。迷ったときは、問題文の例を各演算で実際に計算して、期待値と一致するかで確かめるのが確実です。
まとめ
この問題は、ビット列Aから1を引いてBを作り、AとBのXORでCを作ったあと、AとCをどの論理演算で組み合わせれば最も右の1だけが残るかを問います。1を引くと最も右の1が0になり、その右側の0がすべて1になるため、Cは「最も右の1から右端まで」が1のマスクになります。AとCのANDを取ると、重なる1は最も右の1の桁だけなので、例の00101000から00001000が得られます。XORではBに戻り、ORでは余分な1が残り、NANDでは結果が反転するため、どれも条件を満たしません。
解答・解説
正解はウです
この問題のテーマ
1を引く・XORを取る、という手順でできたビット列Cと元のAを、どの論理演算で組み合わせれば最も右の1だけが残るかを問う問題です。
解き方の考え方
まず、1を引いたときにビット列がどう変わるかを押さえます。Aから1を引くと、最も右の1が0になり、その1より右にある0はすべて1になります。そのため、AとBのXORであるCは「最も右の1の位置と、それより右の全ビット」が1になります。例の00101000ならB＝00100111、C＝00001111です。あとは、AとCを各選択肢の演算で組み合わせ、結果が00001000になるものを選びます。
選択肢ごとの解説
- ×ア 排他的論理和(XOR)排他的論理和（XOR）で組み合わせると、00101000と00001111のXORは00100111になります。CはもともとAとBのXORなので、もう一度AとXORを取るとBに戻ってしまいます。最も右の1だけを残すという目的は達成できません。
- ×イ 否定論理積(NAND)否定論理積（NAND）は、ANDの結果をビットごとに反転したものです。AとCのANDは00001000なので、NANDはその反転の11110111になります。求める値とは0と1が逆になるため、不正解です。
- ○ウ 論理積(AND)論理積（AND）では、Aの1とCの1が重なる桁だけが1になります。Cで1になっているのは最も右の1から右端までの範囲で、その範囲のうちAが1なのは最も右の1の桁だけです（その右側は0）。したがって結果は00001000となり、例と一致します。
- ×エ 論理和(OR)論理和（OR）では、AとCのどちらかが1の桁がすべて1になります。00101000と00001111のORは00101111で、Aの上位にある1も、Cの右側の1も残ります。1が一つだけのビット列にはならないので、不正解です。
補足
負の数を2の補数で表す場合、A AND (−A) でも同じように最も右の1を取り出せます。
POINT
- 2進数から1を引くと、最も右の1が0になり、その右側の0はすべて1になります。
- AとA−1のXORを取ると、最も右の1から右端までがすべて1のマスク（範囲を指定するビット列）ができます。
- ANDは、マスクで1になっている桁だけ元のビットを残す演算で、特定の範囲を取り出すときに使います。
- 迷ったら問題文の例を実際に計算し、それぞれの演算の結果が期待値と一致するかで確かめるのが確実です。