基本情報技術者 2012年春期午前（科目A）問02

問題文

非負の2進数

b_{1} b_{2} ... b_{n}

を

3

倍にしたものはどれか。

🖊️ 解答を隠して解いてみる

選択肢

ア：

b_{1} b_{2} ... b_{n} 0 + b_{1} b_{2} ... b_{n}

（正解）

イ：

b_{1} b_{2} ... b_{n} 00 - 1

ウ：

b_{1} b_{2} ... b_{n} 000

エ：

b_{1} b_{2} ... b_{n} 1

🔒 解説は解答すると表示されます

二進数の3倍演算【午前解説】

正解の理由

与えられた2進数を数値として X とおくと、

X = \sum_{i = 1}^{n} b_{i} 2^{n - i}

で表されます。
左に1ビットシフト（末尾に 0 を付ける）した数は

2 X

に相当します。したがって

3 X = 2 X + X

です。2X は b1b2...bn0、X は b1b2...bn に対応するため、3倍は「b1b2...bn0 と b1b2...bn の和」で表せます。よって正解はアです。

例：b=101（10進で5）なら
2X = 1010 (10進で10)、X = 0101 (5) → 和 = 1111 (15) = 3×5

解法ステップ

問題の2進数を数値 X として定義する。
左に1ビットシフト（末尾に 0 を付加）した表現が 2X に相当することを確認する。
3X = 2X + X を使い、問題の選択肢のどれが 2X + X を表しているかを判定する。
加算後に桁上がりが発生しても式は成り立つため、結果のビット長増加を受け入れて正解を確定する。

選択肢別の誤答解説

ア: b1b2 ... b_n0 + b1b2 ... b_n
正解。前半が 2X、後半が X であり 2X+X=3X を満たす。桁上がりが起きても算術的に正しい。
イ: b1b2 ... b_n00 - 1
これは 4X - 1 に相当し、一般には 3X とは異なる。等しくなるのは X=1 の特殊ケースのみ（例外）。
ウ: b1b2 ... b_n000
末尾に000を付けるのは 8X（=2^3 X）であり 3X とは全く異なる。
エ: b1b2 ... b_n1
末尾に1を付けるのは 2X + 1 で、常に 3X になるわけではない（X に依存するずれがある）。

具体例（b=101 = 5）で確認すると：
ア: 1010 (10) + 0101 (5) = 1111 (15) → 正しく 3×5
イ: 10100 (20) - 1 = 10011 (19) → 19 ≠ 15
ウ: 101000 (40) → 40 ≠ 15
エ: 1011 (11) → 11 ≠ 15

よくある誤解

「末尾に0や1を付けること＝単なる文字列操作」と見なして、加算で生じる桁上がりを無視する。
4倍や8倍に相当する末尾0複数付加（00 や 000）を 3 倍と混同する。
特殊ケース（X=0 や X=1）だけを見て一般解と誤認する（例えば 4X-1=3X は X=1 の特殊解に過ぎない）。

補足コラム

ビット演算的には「左シフト」は高速に乗算（2倍,4倍...）を表現できます。3倍はシフトと加算の組合せ（X<<1 + X）で実装するのが典型です。
実装例（Python）:

def triple_binary(bin_str):
    # bin_str は 'b1b2...bn' のような文字列
    x = int(bin_str, 2)
    return format((x << 1) + x, 'b')  # 左シフトで 2x、+x で 3x
print(triple_binary('101'))  # -> '1111'

桁上がりがあるため、出力ビット長は元の n ビットより n+1 ビット以上になることがある点に注意してください。

FAQ

Q1: 「b1b2...bn0 + b1b2...bn」の表記は文字列の連結と混同してよいですか？
A1: いいえ。これは数値の加算を表します。左側は 2X、右側は X なので算術的な合計を意味します。

Q2: 元の数が 0 の場合はどうなりますか？
A2: X=0 のとき 2X+X=0 であり、どの表記（末尾0付加＋加算）でも0になります。特例ではありませんが一般式に含まれます。

Q3: 桁上がりで桁数が増えた場合、表現はどうなる？
A3: 増えます。例えば 101 の場合は 4 ビット 1111 になります。演算自体は常に正しいので桁数増加を許容してください。

関連キーワード: 2進数、ビットシフト、左シフト、桁上がり、二進法乗算、シフト加算手法、ビット演算、算術シフト

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！