シフトによる除算（2^N で割る = N 回右シフト）

📌

シフトによる除算とは

シフトによる除算は、2 のべき乗で割る場合に限って、右シフトだけで除算を実現するテクニックです。CPUの除算演算よりはるかに高速なため、コンパイラの最適化でよく使われます。

ルール:
・x ÷ 2^N = x >> N
・あふれて捨てられたビットが「余り（剰余）」を表す
・結果は切り捨て除算（整数の世界の割り算）

例: 100 ÷ 4 = ?
・100 = 01100100
・右に2シフト: 00011001 = 25
・あふれたビット: 00 = 0（余り）
・結果: 100 ÷ 4 = 25 余り 0 ✓

⚡

2^N の除算で速い理由

シフトによる除算が CPU で圧倒的に速いのは、シフト命令がビット配線を 1 つずらすだけの単純な回路で実現できるからです。多くの CPU でシフトは 1 クロックで完了します。一方、除算命令は20〜80 クロックもかかる重い処理で、加減乗除の中でも特に遅いことで知られています。

・x ÷ 2 ＝ x >> 1
・x ÷ 4 ＝ x >> 2
・x ÷ 8 ＝ x >> 3
・x ÷ 16 ＝ x >> 4
・x ÷ 2^N ＝ x >> N

2 のべき乗で割るときだけ使えるテクニックですが、よく登場する処理なので意義は大きいです。例: 配列のインデックス計算、画像処理での縮小（縦横 1/2、1/4…）、データの正規化、暗号アルゴリズムの内部処理など。

コンパイラの最適化では、x / 8 のような定数除算を自動的に x >> 3 に置換します。ただし符号付き整数で負数を扱う場合は注意。負数を右シフトすると数学的な意味と微妙にずれる（−5 >> 1 は −2 ではなく −3、下向き切り捨て）ので、コンパイラは補正コードを追加することもあります。

なお、シフトで捨てられた下位 N ビットには余り（剰余）の情報が含まれています。x & (2^N − 1)（AND マスク）で x mod 2^N を求められます。これも剰余演算 (%) より高速です。

✂️

整数除算の切り捨て挙動

シフトによる除算は整数除算なので、小数部分は必ず切り捨てられます。これは数学的な厳密な除算とは違うので、結果の解釈に注意が必要です。

例: 7 ÷ 2 を 1 ビット右シフトで計算
・7 = 0000 0111
・右に 1 シフト → 0000 0011 = 3（小数部分が消える）
・あふれたビット 1 が余り
・結果: 7 ÷ 2 = 3 余り 1（数学では 3.5）

正の数と負の数で挙動が違うのも重要なポイントです。
・正の数: 0 に近い方に切り捨て。例: 7 >> 1 = 3（7/2 = 3.5 → 3）
・負の数: 算術右シフトでは下向き（floor）に切り捨て。例: −5 >> 1 = −3（−5/2 = −2.5 → −3、絶対値で見ると切り上げ）

プログラミング言語の / 演算子は通常「0 に近い方へ切り捨て」する（−5 / 2 = −2）ので、算術右シフトと結果がズレる場合があります。コンパイラが x / 8 をシフトに置換するときに補正を追加するのはこのため。

まとめ:
・「x >> N は x を何で割ったものと等価？」→ 2^N（小数切り捨て）
・「x >> 3 と x ÷ 8 は等価か？」→ 正の数では同じ。負の数では微妙にズレる
・「8 で割った余りを求める方法は？」→ x & 7（下位 3 ビットを AND でマスク）