ITパスポート 令和6年度 問85：algorithmに関する問題

答えは d です。a＝2の(i−1)乗、b＝integerNum ＋ digitNum × exponent。

2進数を10進数に直すときは、各桁に「位の重み」をかけて足していきます。一番右の桁（末尾から1番目）は重み1（＝2の0乗）、その左は2、その左は4…と倍々で増えます。

末尾からi番目の重みは「2の(i−1)乗」になるので、aはこれ。そして計算結果は「今までの合計＋（その桁の数字×重み）」を足し続けるので、bは足し算（＋）です。

👉 覚え方：「桁の重みは右から1,2,4,8…」「重みをかけて“足していく”」。

かけ算でつなぐ選択肢（a・c）は合計が壊れるので不正解です。

なぜこれが正解か

正解は d（a＝2の(i−1)乗、b＝integerNum ＋ digitNum × exponent）。

2進数→整数変換は各桁の値×位の重み（2のべき乗）の総和。ループは末尾からi番目（i=1,2,…）を順に処理する。末尾から1番目の重みは2⁰=1、2番目は2¹、…なので、末尾からi番目の重みは 2の(i−1)乗（＝a）。各桁の寄与 digitNum×exponent を合計に 加算 していくので integerNum ← integerNum＋digitNum×exponent（＝b）。

例 "100"：i=1で末尾の0×1=0、i=2で0×2=0、i=3で1×4=4 → 合計4。正しく4を返す。

各選択肢の解説

• a：aが(2のi乗)−1で重みが誤り、bも乗算で合計が壊れる。
• b：bは加算で正しいが、aの重み(2のi乗)−1が誤り（i=1で重み1にならず1、i=2で3になり不正）。
• c：aは正しいがbが乗算で合計が壊れる。

覚え方・ひっかけ注意

「位の重みは右端から2⁰,2¹,2²…＝末尾からi番目は2の(i−1)乗」「総和は加算で積み上げる」。乗算でつなぐ選択肢は累計が破綻すると見抜く。

理論的背景

本問は2進数文字列を末尾の桁（2の0乗の位）から順に走査して整数値を計算するアルゴリズムの実装問題である。核心は「桁の重みの計算式」にある。2進数のi番目の桁（末尾から数えて）の重みは2^(i-1)（2のi-1乗）である。ループ変数iが1から始まるとき：i=1（末尾1桁目）→重み2^0=1、i=2（末尾2桁目）→重み2^1=2、i=3（末尾3桁目）→重み2^2=4 となり、これが「2の(i-1)乗」という式（a）に対応する。次にintegerNumの更新式（b）：各桁の「値（0または1）×重み」を累積加算するため、integerNum ← integerNum + digitNum × exponent が正解。選択肢aとbの「2のi乗-1」はi=1のとき2^1-1=1で偶然一致するが、i=2のとき2^2-1=3≠2となり不一致。選択肢aとcの「integerNum × digitNum × exponent」は乗算型の更新式で、初期値0に乗算し続けると結果が0のままとなるため不適切（加算が正しい）。

実務での使われ方

2進数→整数変換アルゴリズムは組込みシステム開発・プロトコルパーサ・低レベルI/O処理の基礎として日常的に実装される。実際のプログラムではビットシフト演算子（<<・>>）を使った高速実装（value = (value << 1) | bit の繰り返し）が一般的で、本問のアルゴリズムは教育的な明示的実装パターン。シリアル通信（UART・SPI・I2C）のビットストリームから数値を復元する処理、バイナリファイルのヘッダ解析（魔法数・バージョン番号の解析）、ネットワークパケットのフィールド抽出（IPヘッダのTTL・ProtocolフィールドのビットマスクAND）などで同様のビット操作が使われる。Python・Javaでは`int("101", 2)`・`Integer.parseInt("101", 2)`という組み込み関数で実現できるが、低レベル言語（C・Rust・Assembly）ではアルゴリズムを直接実装する必要がある。

試験での位置づけ

アルゴリズムの穴埋め問題（a, bに入れる字句）はITパスポートの難問カテゴリに属し、プログラムを精密に読んでa・b両方の式を同時に導く必要がある。本問の解法ステップは①末尾からの桁走査という処理の方向を理解する②重みの式を桁インデックスiから導出する③累積加算か乗算かを初期値（0）と更新パターンから判断する——の3ステップが必要。近年のITパスポートはシラバス改訂でアルゴリズム・プログラミング分野の出題比率が増加しており、「プログラムトレース」「穴埋め」「逆算」の3形式が混在して出題される。基本情報技術者（FE）では整数変換・ビット操作・再帰関数・ソートアルゴリズム（クイックソート・マージソート）の計算量分析まで問われる。

選択肢の発展補足

選択肢aの「a=(2のi乗)-1、b=integerNum × digitNum × exponent」は重みの計算とIntegerNumの更新式の両方が誤り。(2のi乗-1)はi=1で1、i=2で3、i=3で7と指数的増加だが2の冪ではなく誤った値。乗算更新式は初期値0があることで全体の結果が0になるため明らかに誤り。選択肢bは重みの計算式だけが誤り（(2のi乗)-1の問題は上述）で更新式は正しい。選択肢cは更新式だけが誤り（乗算型）で重みの計算は正しい。この問題の面白い設計は「a・bがそれぞれ独立に正誤があり、両方正しいdが正解」という構造であり、aとbを別々に検証する必要がある。検証の高速化テクニックとして、具体例（"100"＝4）でトレースしてみると：末尾から走査（0→0、0→0、1→4）で合計4となりdが正しいことを確認できる。