シフトによる乗算（掛け算 = シフト + 加算）

📌

シフトによる乗算とは

シフトによる乗算は、x × N を「左シフトの足し合わせ」だけで実現するテクニックです。CPUの乗算器が存在しなかった時代に使われていた方法で、現代でも特定の最適化で見かけます。

例: 5 × 5 を計算
・5 を 2 進数で書くと 101
・bit 0 = 1 → 5 × 2⁰ = 5
・bit 1 = 0 → 使わない
・bit 2 = 1 → 5 × 2² = 20
・合計: 5 + 20 = 25 ✓ (5 × 5 = 25)

⚡

2^N の乗算で速い理由

N が 2 のべき乗（2, 4, 8, 16, …）の場合、シフトはたった 1 命令で完了します。これは「2 のべき乗の 2 進数表記は 1 ビットしか立っていない」という性質のおかげ。例えば 8 = 1000、16 = 10000 のように。

・x × 2 ＝ x << 1（1 シフト）
・x × 4 ＝ x << 2
・x × 8 ＝ x << 3
・x × 16 ＝ x << 4
・x × 2^N ＝ x << N

なぜ速いのか？ CPU の乗算命令は内部で何ステップもの加算を行う複雑な処理。一方シフト命令はビット配線を 1 つずらすだけの単純な回路で、多くの CPU で 1 クロックで完了します。乗算は通常 3〜10 クロック必要なので、速度差は実測でも数倍〜十数倍。

そのためコンパイラの最適化では、x * 8 のようなコードを自動的に x << 3 に置き換えます。組込みシステムや暗号アルゴリズムでは、明示的にシフトで書くことで性能を引き出します。

ちなみに N が 2 のべき乗でない場合（例: × 10）は、上のビット分解で示したように複数のシフト＋加算で実現します。それでも乗算回路がない単純な CPU よりは高速。歴史的に乗算器のない 8 ビット CPU では、シフト＋加算で乗算ライブラリが書かれていました。

📝

シフト乗算の典型計算

シフトによる乗算には、いくつかの典型的な計算パターンがあります。これらを押さえておくと、すばやく答えを導けます。

・「x << N は x の何倍か？」 → 答え: 2^N 倍。すぐ反射的に答えられるように
・「x × 8 は何ビット左シフト？」 → 答え: 3 ビット（8 = 2³）
・「x × 32 は何ビット左シフト？」 → 答え: 5 ビット（32 = 2⁵）
・「x × 10 をシフトと加算で表せ」 → (x << 3) + (x << 1)（10 = 8 + 2）
・「x × 6 をシフトと加算で表せ」 → (x << 2) + (x << 1)（6 = 4 + 2）
・「x × 7 をシフトと減算で表せ」 → (x << 3) − x（7 = 8 − 1）。引き算が使えると組み合わせが減る

解き方のコツ:
・かける数を2 進数に直す（10 → 1010、6 → 110）
・ビットが 1 の位置 i ごとに x << i を加算する
・あふれに注意。8 ビット符号付きで × 64 を計算するとオーバーフローする可能性