基本情報 令和元年度 秋期 問1：テクノロジ系に関する問題

答えは d です。

10進数を2進数に変換するときの定番テクニック：

• 2で割った余りを下から並べる
• 7÷2＝3余り1、3÷2＝1余り1、1÷2＝0余り1...

流れ図では：

• aの位置：余りを配列に格納 → `NISHIN(i) ← 7 mod 2`
• bの位置：次に商で更新 → `7 ← 7 div 2`

👉 覚え方：10進→2進＝割り算の余りを下から並べる。

ほかの選択肢：a/b/cはmodとdivの順番が逆など、計算手順が崩れる。

なぜこれが正解か

正解は d。10進整数を2進数に変換する標準アルゴリズムは2で割った余りを下位から並べる手順：

```

while (7 > 0) {

NISHIN[i] ← 7 mod 2 // 余り（0または1）を下位ビットから格納

7 ← 7 div 2 // 商で更新

i ← i + 1

}

```

つまり「a：余りを配列に格納、b：商で更新」の順序が正しい。

各選択肢の解説（一般論）

• modとdivの順序が逆だと、商を計算してから余りを取ると元の値が失われ、誤った値が格納される。
• divを先に計算するなら一時変数に格納する必要がある。

覚え方・ひっかけ注意

基数変換の手順を整理：

• 10→2進：2で割った余りを下位から並べる
• 10→16進：16で割った余りを下位から並べる
• 10→8進：8で割った余りを下位から並べる

アルゴリズム実装時は「余り取得→商で更新」の順序を保つことが鉄則。

理論的背景

基数変換は除算法（Division Method）と乗算法（Multiplication Method）の2方式：

• 除算法（整数部）：基数で割った余りを下位から並べる
• 乗算法（小数部）：基数を掛けた整数部を上位から並べる

本問は整数部の除算法。一般化すると、整数 N を基数 b の n 桁で表現する場合：

```

for (i = 0; i < n; i++) {

digit[i] = N mod b

N = N div b

}

```

実装上の注意点

• 桁数制限：本問は8桁固定。上位桁がオーバーフローする値（256以上）は表現できない
• 負数表現：符号付き整数の2進表現は2の補数表現が標準。負数は「全ビット反転＋1」で求める
• 符号付き8bit範囲：-128〜+127
• 浮動小数点：IEEE 754で符号・指数・仮数に分割

関連アルゴリズム

• ホーナー法（Horner's method）：多項式評価の効率化。基数変換にも応用可
• シフト演算：2の冪で割る場合は右シフト（`N >> 1`）が高速。modはAND演算（`N & 1`）
• モジュラー演算：`(a + b) mod m = ((a mod m) + (b mod m)) mod m`、暗号で重要

実務での使われ方

• C/C++/Java：`itoa()`、`Integer.toBinaryString()`等で実装済み
• 競技プログラミング：基数変換問題、桁DP
• 暗号アルゴリズム：モジュラー指数演算、RSA等
• エンコード／デコード：Base64、Base58（Bitcoin）、Base32
• ハッシュ／チェックサム：CRC、Adler-32

試験での位置づけ

基本情報の基礎理論・プログラミング分野で頻出。応用情報・科目B（プログラミング）では再帰的実装、ループの停止条件、配列インデックス管理が問われる。

選択肢の発展補足

ビット演算による高速化：

• `N mod 2` ≡ `N & 1`（最下位ビット）
• `N div 2` ≡ `N >> 1`（右シフト）
• 16進への変換は `N & 0xF` と `N >> 4` で4bitずつ取り出す

組込み系やパフォーマンスクリティカルな場面では除算より高速なため、これらの等価変換は実装の常套手段。基数変換のアルゴリズム理解は、エンディアン（バイトオーダー）・浮動小数点表現・誤差伝播・桁あふれ検出にもつながる基礎中の基礎。