基本情報技術者 2011年 秋期 午前（科目A） 問01

16ビット数を16進の各桁（ニブル）に分けてスタック格納する手順【午前2 解説】

要点まとめ

• 結論：正解は イ。各繰り返しで下位4ビットを取り出すには n AND $000F_{16}$ を使い、次に右に4ビット論理シフトします。
• 根拠：AND $000F_{16}$ が下位ニブルのみを抽出し、右に4ビット論理シフトすることで次の上位ニブルが下位位置に移動します。
• 差がつくポイント：論理シフトと算術シフトの違い、そしてマスクが下位か上位か（$000F$ vs $FFF0$）を誤解しないことが重要です。

正解の理由

• ステップ(1)で

  x = n AND 000F₁₆

  とすれば、$n$ の下位4ビットのみが $x$ に入ります（1桁分の16進値）。
• ステップ(3)で

  n

  を右に4ビット論理シフトすると、元の上位ニブルが下位位置に入り、次回同じ操作で次の桁を取り出せます。
• 左シフトやマスク $FFF{0}_{16}$ を使うと、取り出す値や移動方向が異なり、目的どおりに桁を順に得られません。

よくある誤解

• 論理シフトと算術シフトを混同する：符号ビットを保持する算術右シフトだと負数時に1が詰められ、誤った値になります。符号に依存しない論理右シフトを使うべきです。
• マスクの向きを間違える（$000F$ と $FFF0$ の取り違え）：$FFF0$ は下位4ビット以外を残すマスクであり、単独でニブルを取り出せません。
• 左シフトで桁を移動させようとする誤り：左シフトは下位を0で埋め上げる方向に移動するため、繰り返すと正しい順序の桁が得られません。

解法ステップ

1. 初期値として16ビット数 $n$ を用意する（例：$n=0xABCD$）。
2. 4回繰り返すループを実行する（16ビット ／ 4ビット = 4桁）。
3. 各回で (1) $x=n\&0x000F$（＝$n$ AND $000F_{16}$）で下位ニブルを抽出し、(2) $x$ をスタックにプッシュする。
4. (3) $n$ を右に4ビットの論理シフト（$n\leftarrow n{\gg }_{logical}4$）して、次のニブルを下位位置に移動させる。
5. 4回終われば下位から上位へ順に格納された4桁が得られる。

• 1回目: $x=0xABCD\&0x000F=0xD$ → push 0xD；$n\leftarrow 0x0ABC$（右4ビット論理シフト）
• 2回目: $x=0x0ABC\&0x000F=0xC$ → push 0xC；$n\leftarrow 0x00AB$
• 3回目: push 0xB；$n\leftarrow 0x000A$
• 4回目: push 0xA；終了

# 例: Python（右シフトは論理ではなく符号無し扱いで実施）
n = 0xABCD
stack = []
for _ in range(4):
    x = n & 0x000F
    stack.append(x)   # push
    n = (n >> 4) & 0xFFFF  # 16ビットを意識して論理的に扱う
print([hex(v) for v in stack])  # ['0xd','0xc','0xb','0xa']

選択肢別の誤答解説

• ア（a = n AND $000F_{16}$、b = 左に4ビット）
  下位ニブルを取り出した後に左シフトすると、取り出した下位ニブルは左へ移動し、次回は正しい次のニブルが下位に来ません。したがって正しい順に桁を取得できません。
• イ（a = n AND $000F_{16}$、b = 右に4ビット）
  正解。下位ニブル抽出→右シフトで次のニブルが下位に移動する流れが目的に合致します。
• ウ（a = n AND $FFF{0}_{16}$、b = 左に4ビット）
  マスク $FFF{0}_{16}$ は下位4ビットを切り落とすもので、1桁分の値を得られません。また左シフトも方向が不適切です。
• エ（a = n AND $FFF{0}_{16}$、b = 右に4ビット）
  $FFF{0}_{16}$ は単一ニブルの抽出に使えないため、x に入る値は期待する0〜15の16進1桁にならず不適切です。右シフトしても正しく桁を得られません。

補足コラム

• 代替手法：ビット演算の代わりに算術的に $x=n\mathrm{mod}16$、$n=\lfloor n/16\rfloor$ を用いる方法もあります。高級言語では

  %

  と

  /

  （整数除算）で実装可能です。
• 言語依存の注意：C言語などで右シフト演算子

  >>

  は符号付き整数の場合に算術シフト（符号ビットで埋める）になることがあるので、符号なし型（unsigned）を使うかマスクして論理シフト相当を確保してください。
• スタックの取り出し順：問題文で「下位の桁から順にスタックに格納する」とある場合、POPして取り出すと上位→下位の順になるため用途に応じてFIFO（キュー）や逆順処理を検討します。

FAQ