
武蔵野個別指導塾の特徴
共通テスト情報I 二進数の桁あふれ—固定桁の結果と本来の和を分けて確かめる|武蔵野個別指導塾

固定桁のカウンタで残った列と失った位を分け、元の和へ戻す道筋をたどります。境界で桁あふれを見極めましょう。
高校生が固定桁のカウンタの表示を見て、小さい値に戻ったので足し算を疑う場面を考えます。たとえば、カウンタに入っていた値に別の値を加えると、計算上は増えているのに、保存された列を読むと小さくなることがあります。計算が間違ったのか、保存できる桁数を超えたのかは、表示だけでは決まりません。
ここでは、0以上の整数を表す二進数を使い、各問題で決めた桁数より上が出たら下位の指定桁だけを保存する規則を考えます。問題中のカウンタや数値は、この規則を調べるために作ったものです。保存された値と、桁を捨てる前の本来の和を別々に記録すると、何が起きたのかを追えます。
何を決めて、何を判定するか
問いの型は大きく3つあります。第1は、2つの入力から本来の和と保存される列を求め、桁あふれの有無を判定する型です。先に列の足し算をしても、十進数で和を求めてから二進数に直してもかまいません。ただし、保存の操作は和を求めた後に適用します。
第2は、保存された列と捨てた上位桁を手掛かりに、本来の和や失った量を求める型です。上位桁が示すのは、左側に書かれた数字そのものの量ではありません。その位置の重みを掛けた量です。残った列を十進数に直した値に、この量を戻して確かめます。
第3は、入力の一方を動かし、桁あふれが起きる境界を求める型です。桁数と片方の入力、もう一方の入力範囲を固定し、保存可能な最大値と和を比較します。最大値と同じなら収まり、1大きければ上位に桁が現れます。入力の範囲を問題から読み落とすと、そもそも入力できない値を候補に含めるので注意します。
どの型でも、桁あふれは指定した保存幅に対する判定です。同じ和でも、十分に広い欄なら上位桁を捨てずに済みます。また、小さい保存値を見ただけでは、上位桁が出たかどうかは特定できません。入力や捨てた桁など、和を絞る情報が必要です。
位の重みと保存の境界
二進数は右端から順に、1、2、4、8というように、左へ1桁進むたびに重みが2倍になります。それぞれの桁が1ならその重みを加え、0なら加えません。たとえば4桁の 1010 は、8と2を合わせた十進数の10です。先頭の0も桁数の指定を示すので、省かずに書きます。
図1のように、4桁の保存欄の左隣には重み16の位があります。4桁で表せる最大値は、4つの位がすべて1の 1111、つまり8と4と2と1を合わせた15です。したがって、和が15以下なら4桁に収まり、16以上なら少なくとも重み16の位が必要です。

図1で左隣の位が1なら、その位の値は1ではなく16です。4桁の下位部分を残す規則では、この位を含む左側が保存欄から外れます。失った値は、消えた各位の重みの合計として計算します。
一般に保存幅を n 桁とすると、左隣の位の重みは2を n 回掛けた値です。これを境界の量と呼ぶことにします。保存された値は、その境界の量で本来の和を割った余りです。捨てた上位部分を十進数で読んだ値は商に当たり、本来の和は「商 × 境界の量」と「余り」を合わせて戻せます。割り算を使う方法と、二進数の列を切る方法は同じ境界を見ています。
ただし、保存列だけで商を決めることはできません。同じ余りを持つ和が複数あるからです。入力範囲や上位部分が与えられたときに初めて、候補を絞れます。固定桁への保存は、元の和の情報を一部失う操作です。
基本例題:残った列から和へ戻す
あるカウンタは、0から15までの整数をそれぞれ符号なし4桁で受け取ります。2つの入力を加え、和の下位4桁だけを保存します。入力が十進数の13と7のとき、本来の和を二進数と十進数で、保存列を先頭の0を含む4桁で示してください。捨てた上位部分と、その部分が表す十進数の量も求めます。
まず入力を列にします。13は8と4と1の和なので 1101、7は4と2と1の和なので 0111 です。右端から足し、各位で2になった分を左へ繰り上げると、下のようになります。
1101
0111
------
10100
本来の和は 10100 です。左端の1は重み16、右から3桁目の1は重み4なので、十進数では20です。十進数で入力を足しても13と7の和は20となり、一致します。
図2のように、保存するのは右側の4桁 0100 です。その左の1は保存欄から外れます。0100 の十進数の値は4、捨てた1が表す量は16です。両者を合わせると20になり、本来の和へ戻ります。

図2の左側の1は、保存欄にそのまま追加される数字ではありません。欄に収まらなかった位を、説明のため別に書いています。20を16で割れば商1、余り4です。商1に16を掛け、余り4を加えると20となることも、列の分割と一致します。
表示された4は、元の13より小さい値です。それでも加算前の値が減ったと判断するのは早すぎます。ここで小さくなったのは保存後に読んだ値であり、本来の和は20です。逆に、保存列が正しいからといって、本来の和が4だったと決めることもできません。どの段階の値かを言葉で添えておくと、2つの答えが混ざりません。
境界と復元をもう一歩追う
標準例題:どこから桁あふれか
0から31までの整数をそれぞれ符号なし5桁で入力し、和の下位5桁だけを保存します。一方の入力は十進数の23、もう一方は0から12までの整数です。桁あふれが起きる後者の入力をすべて求め、そのうち最小の入力での保存列を5桁で答えてください。
5桁の最大値は 11111 で、16、8、4、2、1の和の31です。23に加えて31以下に収まるのは、もう一方が8以下のときです。入力が9なら本来の和は32となり、二進数では 100000 です。左端を捨てた保存列は 00000 です。
入力がさらに大きければ和も大きくなるので、指定範囲で桁あふれが起きる入力は9、10、11、12です。端の12でも入力可能な範囲内で、和35は32以上です。一方、8なら和31で 11111 がそのまま収まります。境界の両側を確かめると、不等号の向きを誤りにくくなります。
32から捨てた左端の1は、5桁の左隣の重み32を表します。保存値0に32を戻せば、最小の桁あふれの場合の和32です。保存列がすべて0でも、本来の和が0とは限らないことが見えます。
発展例題:上位部分を手掛かりに戻す
0から63までの整数をそれぞれ符号なし6桁で入力し、和の下位6桁だけを保存します。保存列が 001011 で、捨てた上位部分は1だったとします。本来の和を十進数で求め、入力の一方が十進数の46なら他方はいくつか答えてください。入力が条件の範囲に入ることも確認します。
6桁の左隣の重みは64です。保存列 001011 は8と2と1を合わせた11なので、捨てた部分の64を戻した和は75です。46に29を加えると75ですから、もう一方の入力は29です。46と29はいずれも0から63の範囲にあります。
列でも戻します。46は 101110、29は 011101 です。両者の和は 1001011 となり、右側の6桁は 001011、左側は1です。計算した入力を元の条件に戻し、保存列と捨てた部分の両方を満たすことまで確認します。
上位部分が与えられなければどうでしょうか。保存列が同じでも、和11と和75はどちらも下位6桁が 001011 です。問題の入力範囲や一方の入力が別途わかるなら候補を絞れますが、保存列だけから元の和を一意に決めることはできません。上位部分の情報は、復元に必要な条件の一つです。
誤答を保存境界まで戻して直す
基本例題の和 10100 について、「捨てたのは1だから、保存値4に1を足して本来の和は5」と答えたとします。間違いは足し算の前に、捨てた1を右端の位の1として扱ったところにあります。図3のように、その1は4桁の保存欄の左隣にあり、重みは16です。

図3で示した位置は、文字としては同じ1でも、右端とは役割が違います。修正するときは、まず保存欄を右から4桁に区切ります。次に外側の1の位置に16という重みを書き、保存値4と合わせて20に戻します。答えが入力13と7の和にも一致すれば、切る位置と重みを両方照合できます。
別の誤りは、本来の和が保存可能な最大値と同じときにも桁あふれとすることです。最大値は実際に保存できる列ですから、その値自体は収まります。超えたときに初めて保存欄の左側に1が必要になります。最大値と、その次の整数をそれぞれ列にして比較すれば、境界での取り違えを直せます。
練習:保存欄の外まで追う
各問とも入力は符号なし整数で、指定された桁数の範囲内です。和はまず桁数を制限せずに求め、その後に指定桁数の下位部分だけを保存します。二進数の保存列は先頭の0を省かずに答えてください。
- 3桁のカウンタに十進数の5と2を入力します。入力範囲はそれぞれ0から7です。本来の和、3桁の保存列、桁あふれの有無を答えてください。
- 4桁の記録欄に十進数の11と6を入力します。入力範囲はそれぞれ0から15です。本来の和、4桁の保存列、捨てた上位部分が表す量を答えてください。
- 5桁の欄に十進数の19と、0から20までの整数を入力します。各入力の許容範囲は0から31です。桁あふれが起きる後者の整数をすべて示し、境界の前後の保存列を各5桁で答えてください。
- 6桁の欄で、保存列は 000101、捨てた上位部分は1でした。入力はそれぞれ0から63の整数で、一方は37です。本来の和と他方の入力を十進数で求め、列でも条件を確かめてください。
- 4桁の欄に入る2つの入力はそれぞれ0から15の整数です。保存列が 0010 であるとき、本来の和として可能な値をすべて十進数で答え、それぞれを実現する入力の組を1組ずつ示してください。
練習の答えと道筋
-
5は 101、2は 010 です。和は二進数 111、十進数7で、保存列は 111 です。上位に桁は現れず、桁あふれはありません。保存値7は入力の和7に一致し、3桁の最大値にも等しくなります。
-
11は 1011、6は 0110 です。和は 10001、十進数17です。保存列は 0001、捨てた上位部分は1で、重み16の位にあるため失った量は16です。保存値1に16を戻すと17で、入力の和とも一致します。
-
5桁の最大値は31です。19に12を加えると31で、保存列は 11111 です。13を加えると32になり、和 100000 の下位5桁は 00000 です。よって桁あふれが起きるのは13から20までの整数です。上端の20でも和39は32以上であり、指定された候補の範囲外には広げません。
-
6桁の左隣の重みは64で、保存列 000101 の値は5です。本来の和は64と5を合わせた69です。69から37を引くと他方は32で、許容範囲内です。37は 100101、32は 100000 なので、和は 1000101 です。左の1と右側の 000101 に分けると、問題の両条件を満たします。
-
4桁の境界の量は16で、保存列 0010 の値は2です。2入力の和は0から30までなので、2に16の倍数を加えた候補のうち範囲内なのは2と18です。たとえば2は1と1、18は8と10の和です。後者は 1000 と 1010 の和 10010 となり、下位4桁は 0010 です。さらに16を加えた34は入力の和の上限30を超えるため候補に入りません。
ここだけ残す
- 先に本来の和を求め、保存幅の右側から区切ります。
- 捨てた桁は、元の位置の重みで量に直します。
- 保存値と失った量を合わせ、入力の和に戻して照合します。
- 最大値は収まり、その次の値から桁あふれが起きます。
- 保存列だけで本来の和が決まるとは限りません。
答えの途中からつまずきを見つける
保存列が違うときは、まず和の列を隠さず書き、右端から指定桁数を数えているかを見ます。和の段階ですでに違うなら、繰り上がりをどの位に渡したかを確かめます。和は正しいのに十進数の復元だけが違うなら、捨てた1に付けた位の重みを尋ねます。
個別に説明を聞くときは、最大値そのものと1大きい値の両方を並べ、どちらから保存欄の左に桁が必要かを言葉にしてもらいます。さらに保存列と上位部分を合わせて元の和に戻せるかを確認します。数だけを合わせるのでなく、保存前と保存後を区別できれば、小さく戻った表示の理由を筋道立てて説明できます。
もう「日東駒専」を目標にしないでください。
武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。
まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。
本気になった日が、入塾の日。
お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。
電話は年中無休。365日、24時間、お電話可能。




