シフト演算で 2 倍 / 半分
シフト演算で 2 倍 / 半分
このレッスンで分かること
- 10 進数で
123を 10 倍するには右に0を 1 つ付け足して1230にすれば良いですよね- シフト演算は CPU の基本命令の 1 つで、低レベルでは「2 のべき乗倍」を表すときに自然と登場します
- 左シフト
n << kはnを2^k倍する 操作です
シフト演算で 2 倍 / 半分 とは
左シフトと右シフトで 2 のべき乗倍 / 除算を高速に行う仕組みを学び、シフト演算による倍率変換を実装する。
10 進数で 123 を 10 倍するには右に 0 を 1 つ付け足して 1230 にすれば良いですよね。2 進数でも同じ発想で、右に 0 を 1 つ付け足すと 2 倍 になります。これがビットの 左シフト です。逆に、右端の桁を 1 つ落とすと 半分 (整数除算) になります。これが 右シフト です。
シフト演算は CPU の基本命令の 1 つで、低レベルでは「2 のべき乗倍」を表すときに自然と登場します。ただし現代の最適化環境では n * 2 と n << 1 で体感差が出ないことが多く、書きやすさで * 2 を選ぶ場面もよくあります。シフト記法は性能のためというより、ビットを直接ずらしている という意味合いを伝える表現として覚えておくと良いです。
シフトは「2 のべき乗の掛け算 / 割り算」をビット単位で表す基本操作。速度よりも「ビットをずらしている」意図を読み取れるかが大事。
左シフト <<
左シフト n << k は n を 2^k 倍する 操作です。
1 << 0 = 11 << 1 = 21 << 2 = 41 << 10 = 1024(= 1 KB)1 << 20 = 1048576(= 1 MB)
2 進数では、ビットがそのまま左にずれます。
0011 << 1 = 0110(3 -> 6)0011 << 2 = 1100(3 -> 12)
右シフト >>
右シフト n >> k は n を 2^k で割った商 (小数切り捨て) です。
8 >> 1 = 48 >> 2 = 28 >> 3 = 17 >> 1 = 3(= 7 / 2 の整数商)
2 進数では、ビットがそのまま右にずれて、右端のビットは落ちて消えます。
1100 >> 1 = 0110(12 -> 6)1100 >> 2 = 0011(12 -> 3)
図のポイント (テキスト併記)
-
左シフトはビットが左にずれて 2 倍、右シフトはビットが右にずれて半分
左シフトはビットが左にずれて 2 倍、右シフトはビットが右にずれて半分。落ちたビットは消える。
符号付き / 符号なし右シフト
ここで注意すべきは 負数の右シフト です。多くの言語では >> は 算術右シフト (符号ビットを保持) で、JavaScript には >>> という 論理右シフト (符号ビットを 0 で埋める) もあります。
-8 >> 1は-4(符号維持)- JavaScript の
-8 >>> 1は2147483644(符号ビットを0で埋める)
C、Java、Go なども >> は算術右シフトで、Java は >>> を符号なし右シフト用に持っています。Python は任意精度整数なので >> は常に符号維持され、>>> は存在しません。
Python での実装
本レッスンの題材は「n を k ビット左シフトして返す」関数です。中身は n << k 1 行だけですが、シフトの感覚を掴むのに最適です。
Python
def multiplyByPow2(n, k):
return n << kJavaScript での実装
JavaScript
function multiplyByPow2(n, k) {
return n << k;
}JavaScript のビット演算は 32 ビット整数として行われる点に注意してください。たとえば 1 << 31 は -2147483648 (32 ビット符号付き整数の最小値) になります。大きな数値を扱うときは BigInt か別の方法を検討する必要があります。
よくある間違い
1 つ目は シフト = 必ず速い、と思い込む こと。最近のコンパイラ / インタプリタは賢く、明示的に << を書いても * 2 と差がほぼないことも多いです。可読性とのバランスで選びましょう。2 つ目は 負のシフト量 n << -1 を渡してしまうケース。C/C++ では未定義動作、Python は ValueError、Java や JavaScript ではシフト量がビットマスクされるなど言語によって挙動が異なります。3 つ目は オーバーフロー。C/C++ では 1 << 32 のようにビット幅以上のシフトは未定義動作になります。一方 JavaScript や Java ではシフト量が剰余されるため、1 << 32 は 1 になります。
実用例
- アライメント メモリアドレスを
4バイト境界に揃えるには(addr + 3) & ~3のようにシフトと AND を組み合わせる - ハッシュ計算 ハッシュ関数の内部で繰り返しシフトと XOR を行う
- 画像処理 RGB の各成分を 8 ビットシフトで詰め込み / 取り出し (
rgb = (r << 16) | (g << 8) | b) - 暗号 多くのブロック暗号でシフトが基本操作として使われる
- キャッシュライン のサイズ計算や ページサイズ の計算 (通常
4 KB = 1 << 12)
シフトはアライメント、ハッシュ、画像処理、暗号などあらゆる低レベル処理で活躍する。
やってみよう
multiplyByPow2(1, 10)が1024になることを確認。これは1 KB。multiplyByPow2(1, 20)で1 MB(1048576)、(1, 30)で1 GB(1073741824)。- 逆に
n >> 3で 8 分の 1 になることを試す。64 >> 3 = 8。 - RGB 値を組み立てる
(255 << 16) | (128 << 8) | 64を計算してみる。16744512という値が得られる。
シフトはビット演算の中で最も使用頻度が高い 1 つ。AND / OR / XOR と組み合わせて自在に操れるようになりましょう。
よくある質問
Q. ビット演算は実務でいつ使いますか？
A. フラグ管理（permission の rwx）、画像処理（マスク）、ハッシュ計算の高速化などで使います。複数の真偽値を 1 つの整数にまとめると、メモリ削減と演算高速化の両方が得られます。例えば 8 個の権限を 1 byte で表せます。
Q. AND / OR / XOR の代表的な使い道は？
A. AND は「特定ビットの確認・抽出」（flags & PERM_READ）、OR は「ビットの立て上げ」（flags |= PERM_WRITE）、XOR は「ビット反転や暗号化」で使います。XOR は 2 回かけると元に戻る性質から、簡易暗号や両端ポインタの入れ替えなどに応用できます。
Q. シフト演算で割り算しても良いですか？
A. 正の整数の 2 のべき乗での除算なら x >> n と x / (1<<n) は同じ結果になります。ただし負の数では言語ごとに挙動が違う（算術シフトと論理シフトの区別）ため、可読性と安全性のために通常の演算子を使い、性能ボトルネックでのみシフトを検討してください。
次のレッスン
次は 16 進数から 10 進数への変換 に進みましょう。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- シフト演算 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. シフト演算 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- n と k は 0 以上の整数 (k は 30 未満)
- ビット左シフト (<<) を使うこと。*, **, pow は使わない
- 戻り値は整数
入出力例
test-cases.txt
multiplyByPow2(3, 2) → 12
multiplyByPow2(1, 0) → 1
multiplyByPow2(1, 10) → 1024
multiplyByPow2(5, 3) → 40
multiplyByPow2(0, 5) → 0
multiplyByPow2(7, 4) → 112
multiplyByPow2(1, 20) → 1048576