冬期講習 2026-2027、募集中。総復習は売りません。90分×完全1対1で、穴だけを塞ぎます 詳しく →
電話 0422-27-7828チャットで質問無料相談を予約

武蔵野個別指導塾の特徴

中学受験算数 二進法の上限つきの数—左の桁から比べて範囲に入る候補を絞る|武蔵野個別指導塾

学習のイメージ写真 武蔵野個別指導塾
X LINE Facebook

1の個数をそろえた候補を左から比較し、境界を含むかどうかまで考える二進法です。

よくあるのは、二進法の札から1が決まった個数ある数を選び、上限より大きい札まで残してしまう場面です。たとえば上限が1010のとき、1100はどちらも1が2個ですが、左から2桁目で上限を超えます。1の個数は必要な条件の一つで、大小も別に調べます。正整数を先頭に0を付けずに表す約束で、どの候補が境界を越えるかを追いましょう。

上限と個数を一緒に見る

問いには、上限以下を選ぶ型と、上限未満を選ぶ型があります。「以下」は上限と等しい数を含み、「未満」は等しい数を含みません。どちらも上限より大きい数は入りません。まず問題の言葉に印を付け、等号が必要かを決めます。

もう一つの型は、同じ桁数の候補を、上限より小さい部分と上限に等しい部分に分けるものです。上限より桁数が少ない正整数は、先頭に0を付けない表し方なら必ず上限より小さくなります。ただし、1の個数という条件は短い数にも適用します。桁数だけで全部を答えに入れることはできません。

二進法では使う数字は0と1です。右端から位の重みは1、2、4、8、16と、左へ行くたびに2倍になります。各位の数字が1ならその重みを取り、0なら取らず、取った重みを足すと十進法の値になります。数の大小を確かめる別の方法として、この合計を使えます。

最初に違う桁で大小が決まる

同じ桁数の二進数を左から比べ、初めて違う位を見ます。そこで候補が0、上限が1なら候補は小さくなります。候補が1、上限が0なら候補は大きくなります。それより右の数字は、すでに決まった大小を逆転できません。

理由を位の重みで考えます。たとえば8の位で違うとき、右の4、2、1の位を全部足しても7です。8の位の差を埋めるには足りません。16の位なら右側の合計は8 + 4 + 2 + 1で15です。同じ仕組みが続くので、最初に違う位だけで判定できます。図1では上限1010と候補1001を比べています。

図1 二進数を左から比較して最初に違う位を見つける図

図1では左から3桁目で候補が0、上限が1です。右端は候補の方が大きくても、そこで決まった大小は変わりません。十進法に戻しても上限は10、候補は9で、同じ結論です。全部の桁が同じなら等しいので、「以下」には入れ、「未満」には入れません。

計算のために短い数の左に0を補って位をそろえることはできます。しかし、その0を桁数に数えません。たとえば11を0011と並べて比較しても、もとの正整数の表記は2桁です。0自体は正整数に含めず、先頭0の付いた別表記を別の候補として数えないようにします。

基本例題:同じ桁数から境目を探す(標準)

上限を二進法の1010とします。先頭に0を付けない正整数で、1010以下、かつ二進表記に1がちょうど2個ある数を、二進表記ですべて挙げ、何個か答えてください。

まず1が2個あるには少なくとも2桁必要です。上限は4桁なので、2桁、3桁、4桁に分けます。桁数の異なる分類は重ならず、上限を超える桁数は候補にならないので、これで調べる範囲を尽くせます。

2桁では先頭が1で、残りも1です。候補は11です。 3桁では先頭が1で、残り2か所のどちらかに1を置きます。候補は101、110です。 4桁では先頭が1で、残り3か所のどこか1か所に1を置きます。候補は1001、1010、1100です。

図2の4桁の欄で、上限と比べます。1001は左から3桁目で小さく、1010は等しく、1100は左から2桁目で大きくなります。以下なので等しい1010を残し、1100を除きます。

図2 四桁の候補を上限と比較して残す境界の図

残る数は11、101、110、1001、1010の5個です。十進法では順に3、5、6、9、10です。上限は10なので、いずれも範囲内です。除いた1100は12で、1が2個でも上限を超えます。上限を未満に変えるなら1010も除き、4個になります。

標準例題:等しい数を含めない(やや難)

上限を二進法の1100とします。先頭に0を付けない正整数で、1100未満、かつ1がちょうど2個ある数を二進表記ですべて挙げ、何個か答えてください。

上限は4桁です。2桁の候補は11です。 3桁の候補は101、110です。どれも4桁の上限より小さい数です。 4桁では先頭の1のほかに1を1個置くので、1001、1010、1100です。 1001は左から2桁目で上限より小さくなります。 1010も左から2桁目で上限より小さくなります。 1100は上限と等しいので、未満には入りません。 したがって11、101、110、1001、1010の5個です。

値に戻すと上限は12、残った数は3、5、6、9、10です。等しい1100は12なので、未満では外れます。「以下」に変えれば1100も入り6個です。等しい候補がそもそも1の個数の条件を満たさないときは、以下と未満で答えが変わらないことにも注意します。

発展例題:上限と同じ桁から枝分かれ(難)

上限を二進法の10110とします。先頭に0を付けない正整数で、10110以下、かつ1がちょうど3個ある数を、二進表記ですべて挙げ、何個か答えてください。

1が3個必要なので、3桁から5桁までを調べます。先頭は必ず1です。各桁数で残りの位から1を置く2か所を選べば、候補を重ねずに尽くせます。

3桁は111の1個です。 4桁は1011、1101、1110の3個です。 これらは5桁の上限より小さく、個数の条件も満たします。 5桁では残り4か所から2か所を選びます。 候補は10011、10101、10110、11001、11010、11100です。 10011は左から3桁目で上限より小さくなります。 10101は左から4桁目で上限より小さくなります。 10110は上限と等しく、以下なので残します。 11001、11010、11100は左から2桁目が上限の0より大きく、除きます。

答えは111、1011、1101、1110、10011、10101、10110の7個です。十進法では7、11、13、14、19、21、22で、上限の22以下です。除いた3個は25、26、28で、いずれも上限を超えます。最後に残った数字の1を数え直すと、どれも3個です。

同じ5桁を上限の左側から分類する方法もあります。最初の1の後、2桁目を1にすると上限の0より大きいので、その先をいくら工夫しても対象外です。2桁目を0にして上限とそろえた場合だけ、次の位を比べます。3桁目で0を選べば上限より小さいことが確定し、残りは1の個数だけを調べます。3桁目を1にした枝では、さらに右へ比較を続けます。小さいことが確定した枝と、まだ等しい枝を混ぜないと、調べる箇所が見えます。

候補がない枝も数える前に確かめる

発展例題の5桁を左から追うと、上限と同じ1011まで進んだとき、すでに1は3個あります。残る右端を0にすれば上限10110と等しく、条件に合います。右端を1にすると1が4個になり、上限も超えるため、どちらの条件から見ても除かれます。残す枝がない場所を0個と記録すれば、無理に候補を作る必要はありません。

一方、最初に小さくなった枝でも、残りの場所が足りなければ条件を満たせません。たとえば残り1か所にあと2個の1を置くことはできません。大小が決まった後も、必要な1の個数と空いている位の数を比べることで、数え漏れや余分な候補を防げます。上限を超えた枝は個数が合っていても戻さず、まだ等しい枝は次の位で再び比較します。

誤った候補を境界に戻す

基本例題で「11、101、110、1001、1010、1100の6個」とした答えを考えます。1の個数だけを数えれば、6個とも条件に合っています。しかし1100と1010を左から比べると、2桁目は1と0です。図3のように、ここですでに1100が大きいと決まります。

図3 個数は合っても上限を超える候補を除く比較図

1100の右側にある0を見て小さいと判断してはいけません。先に違った2桁目の重みは4で、それより右の重みの合計は2 + 1で3です。右端まで含めても差は逆転しません。十進法に戻せば1100は12、上限1010は10なので、問題の場面でも条件を満たさないことがわかります。

逆に、すべての位が上限の対応する位以下でなければならない、と考えるのも誤りです。1001は右端が上限1010の右端より大きいものの、その前の位ですでに小さいと決まっています。比較は各位を独立に判定するのでなく、左から初めて違う位まで続けます。

また、上限が含まれるかを考えずに、常に上限と等しい候補を消すのも誤りです。まず個数と正整数の条件を調べ、それらを満たす上限自身を、以下なら残し未満なら消します。上限が1の個数の条件に合わない場合は、境界の言い方を変えても候補は増減しません。

練習:札の条件を判定する

どの問題も二進法の正整数を先頭に0を付けずに表し、指定された1の個数をちょうど満たすものを考えます。上限は二進表記です。答えは二進表記の全候補と個数で示してください。

  1. 上限1001以下で、1が2個の数をすべて挙げてください。
  2. 上限111未満で、1が2個の数をすべて挙げてください。
  3. 上限10000以下で、1が1個の数をすべて挙げてください。
  4. 上限10101未満で、1が3個の数をすべて挙げてください。
  5. 上限1101以下で、1が3個の数をすべて挙げてください。

練習の答えとたどり方

  1. 11、101、110、1001の4個です。3桁以下の候補は11、101、110です。4桁の1001、1010、1100のうち、上限1001以下は1001だけです。値は順に3、5、6、9で上限の9以下です。

  2. 11、101、110の3個です。2桁の11と3桁の101、110は、いずれも上限111より小さく、1は2個です。上限111には1が3個あるため、以下に変えても追加されません。値は3、5、6で、上限の7未満です。

  3. 1、10、100、1000、10000の5個です。1が1個だけなら、先頭が1で残りはすべて0です。上限は5桁なので1桁から5桁まで各1個あり、5桁の10000は等しいので残します。値は1、2、4、8、16で、上限は16です。

  4. 111、1011、1101、1110、10011の5個です。3桁では111、4桁では先頭以外に2個の1を置く3通りが入ります。5桁の候補は10011、10101、10110、11001、11010、11100です。このうち上限10101より小さいのは10011だけです。10101は等しいので未満には入らず、残りは大きくなります。値は7、11、13、14、19で、上限の21未満です。

  5. 111、1011、1101の3個です。3桁は111です。4桁の候補は1011、1101、1110で、最後の1110は左から3桁目で上限1101を超えます。1101は等しいので残します。値は7、11、13で上限の13以下です。

覚えておくこと

どの位で迷ったかを確かめる

個別指導で確かめるときは、基本例題の1100について、上限と初めて違う位を本人に指して説明してもらいます。1の個数が合うことと、範囲に入ることを別々に言えるかを見ると、どちらの条件で迷ったかがわかります。次に1001の右端だけを見ると誤る理由を、前の位の重みを使って説明できるか確かめます。

境界で迷う場合は、1010が上限と等しいことを確かめてから、「以下」と「未満」で残すかを言い直します。短い11を0011とそろえた場合には、補った0を桁数に入れない理由も確認します。左からの比較と元の条件への戻し方がそろえば、境界の一つ手前も上限自身も区別できます。

集団塾で沈んだ子を、ここから浮上させます。

武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。

まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。

本気になった日が、入塾の日。

お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。

電話は年中無休。365日、24時間、お電話可能。

チャットで質問チャット
無料相談を予約する 電話 0422-27-7828電話 LINE チャット
で質問