平成25年度 春期 午前 問1

✓ これが正解イ2n

解説

掛け算の桁数は足し算になり、2 乗は 2n ビットです。

n ビットで表せる正の整数の最大は、すべての位が 1 のときで、2 の n 乗から 1 を引いた値です。これを 2 乗しても 2 の 2n 乗には届きませんので、b は高々 2n ビットに収まります。小さい数で確かめると見通しが立ちます。n が 3 のとき a の最大は 7 で、7 を 2 乗した 49 は 6 桁ですから、ちょうど 2n です。n が 4 のとき a の最大は 15 で、15 を 2 乗した 225 は 8 桁になり、やはり 2n です。a が小さいときは桁数がこれより短くなりますから、設問は上限を聞く形になっています。ここで効いているのは、掛け算をすると桁数が足し合わされるという性質です。10 進数でも 3 桁どうしの積は高々 6 桁ですから、同じ数を掛ける 2 乗では n と n を足した 2n が上限になります。2 進数のビット数を指数と取り違えないことが、この問の分かれ目です。

ほかの選択肢はなぜ違うのか

• アn＋1：n＋1 は、値を 2 倍にしたときの上限です。2 倍では位が 1 つしか増えませんが、2 乗は同じ大きさの数どうしを掛けますので、増え方がまるで違います。
• ウn²：n² はビット数そのものを 2 乗した形です。2 乗されるのは表される値のほうで、桁数は足し合わされます。n が 4 なら 16 になってしまい、実際の 8 と合いません。
• エ2ⁿ：2ⁿ は桁数と指数を取り違えた形です。n が 10 なら 1024 という極端な値になり、最大値どうしの積が 20 桁に収まるという事実と噛み合いません。