分野 ：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

流れ図を見ると、被乗数がX、乗数がY、結果としてZを出力するので「X × Y ＝ Z」が成立すれば良いことがわかります。

細かな説明がない流れ図の穴埋めでは論理的に答えを導くのは難しいので、XおよびYにトレースが簡単な数値を設定して、出力Zが適切な値かどうかで正しい組合せを探すのが確実な解法です。ここではX＝3，Y＝3を使います（16ビット表記だと「0000 0000 0000 0011）。また、あるビット列を左に1ビットシフトすると2倍、右に1ビットシフトすると1／2したのと同じになります（ビットあふれは無視します）。

• 1. Yの0ビット目は1なので、Z←(0＋3) //Z＝3
  2. Xを1ビット左シフト //X＝6
  3. Yを1ビット右シフト //Y＝1
  4. i←(1＋1) //i＝2
  5. Yの第0ビットは1なので、Z←(3＋6) //Z＝9
  6. Xを1ビット左シフト //X＝12
  7. Yを1ビット右シフト //Y＝0
  8. 以後、Yの第0ビットはi>16になるまで0なので、加算は行われずにループ終了
  9. Zを出力する //Z＝9
• 1. Yの第0ビットは1なので、Z←(0＋3) //Z＝3
  2. Xを1ビット右シフト //X＝1
  3. Yを1ビット左シフト //Y＝6
  4. i←(1＋1) //i＝2
  5. Yを左にシフトすると第0ビットに0が挿入される。以後、Yの第0ビットはi>16になるまで常に0なので、加算は行われずにループ終了
  6. Zを出力する //Z＝3
• 1. Yの第15ビットは0なので加算はなし
  2. Xを1ビット左シフト //X＝6
  3. Yを1ビット右シフト //Y＝1
  4. i←(1＋1) //i＝2
  5. Yを右にシフトすると第15ビットには0が挿入される。以後、Yの第15ビットはi>16になるまで常に0なので、加算は行われずにループ終了
  6. Zを出力する //Z＝0
• 1. Yの第15ビットは0なので加算はなし
  2. Xを1ビット右シフト //X＝1
  3. Yを1ビット左シフト //Y＝6
  4. i←(1＋1) //i＝2
  5. Yの第15ビットは0なので加算はなし
  6. Xを1ビット右シフト //X＝0
  7. Yを1ビット左シフト //Y＝12
  8. Xが0になったので、加算処理が行われたとしてもZは0のままでループ終了
  9. Zを出力する //Z＝0

唯一"3×3"の正しい結果である"9"を出力する「ア」の組合せが適切とわかります。

このアルゴリズムを一言で言うならば、Yの第nビットが1であれば、ZにX×2ⁿを加算する処理を繰り返すものということになります。

おまけとしてこのアルゴリズムをJavaScriptで実装したソースプログラムを掲載します。実行環境で数値やシフト部分を変えてお試しください。