最終更新日:2026年11月18日
fe fe-technology algorithm
まず結論
シフト演算とは、ビット列を左または右にずらす操作です。
基本情報技術者試験では、まず次の関係を押さえます。
左シフト
→ 2倍方向
右シフト
→ 2で割る方向
さらに、右シフトでは 論理シフトか算術シフトか を確認します。
論理右シフト
→ 左側を0で埋める
算術右シフト
→ 符号を保つように左側を埋める
特に16進数の値をシフトする問題では、無理に16進数のまま動かさず、
16進数
→ 2進数に直す
→ シフトする
→ 4ビットずつ16進数へ戻す
とすると安全です。
直感的な説明
シフト演算は、ビット列を横にずらす操作です。
例えば、次の2進数を考えます。
0000 0110
これは10進数で 6 です。
1ビット左にずらすと、
0000 1100
となり、10進数では 12 です。
つまり、1ビット左シフトは2倍のイメージです。
反対に、
0000 1100
↓ 右に1ビット
0000 0110
とすると、12 が 6 になります。
交互に並ぶ 1010...10 を右シフトすると?
FEでは、シフト演算と 2^m - 1 を組み合わせて考える問題もあります。
例えば、1と0が交互に並ぶ6ビットの値を考えます。
x = 101010₂
x / 2 = 010101₂
--------
合計 = 111111₂
この x は末尾が0なので偶数です。したがって x / 2 は、2進数では 右に1ビットずらした値として読めます。
すると、x の1がある位置と x / 2 の1がある位置がちょうど交互に埋まり、足した結果は すべてのビットが1 になります。
111111₂
= 2⁵ + 2⁴ + 2³ + 2² + 2¹ + 2⁰
= 2⁶ - 1
一般に、2n ビットすべてが1なら、
111...111₂
↑ 2nビット
= 2^(2n) - 1
です。
動かして確認:nを変えると、なぜ全部1になる?
nを動かすと、xの桁数が2nビットに変わります。x/2との1の位置がどう埋まるかを見てください。
1010100101011111116ビットすべてが1なので、合計は 2^6 - 1 = 63 です。
見るポイント:xの1とx/2の1が重ならず、0だった位置をちょうど埋めます。だから桁上がりなしで全部1になります。
この形を見抜ければ、試験では長い式変形をしなくても、
1010...10
↓ 2で割る(右へ1ビット)
0101...01
↓ 足す
1111...11
↓
2^(2n) - 1
と判断できます。
「nビットすべてが1なら最大値は 2^n - 1」という考え方は、nビットで表せるパターン数でも整理しています。
論理右シフトは「左から0を入れる」
例えば、16ビットの値が次のビット列だったとします。
1010 1011 1100 1101
これを2ビット右へ論理シフトすると、右端の2ビットは外へ押し出され、左側には 0 が入ります。
1010 1011 1100 1101
↓ 2ビット論理右シフト
0010 1010 1111 0011
4ビットずつ区切って16進数へ戻すと、
0010 → 2
1010 → A
1111 → F
0011 → 3
→ 2AF3
となります。
ここで大切なのは、論理シフトでは元の最上位ビットが1でも、空いた左側は0で埋めることです。
右シフトは「次に見るビットを右端へ持ってくる」操作でもある
ビット取り出し問題では、右シフトは値を半分にするためだけに使うわけではありません。
例えば、16進数 F0C3 を下位から1桁ずつ見るとします。
F | 0 | C | 3
↑
今見る桁
次に C を見たいなら、値全体を右へ4ビット動かします。
ビットを6桁ずつ取り出す際の商と余りの使い方は、UTF-8の3バイト符号化で確かめられます。
F | 0 | C | 3
↓ 右へ4ビット
0 | F | 0 | C
↑
次に見る桁
つまり、
今の4ビットを処理
↓
右に4ビットシフト
↓
次の4ビットが右端へ来る
という流れです。
下位4ビットの取り出しには、ビットマスクとは? のAND演算を組み合わせます。
値 AND 000F₁₆
→ 今の下位4ビットを取り出す
値を右に4ビット論理シフト
→ 次の4ビットを下位へ持ってくる
定義・仕組み
シフト演算では、ビット列を指定した方向へ移動します。
| 操作 | 意味 | 数値のイメージ |
|---|---|---|
| 左シフト | ビット列を左へずらす | 2倍、4倍、8倍 |
| 右シフト | ビット列を右へずらす | 1/2、1/4、1/8 |
左シフト
1ビット左にずらすと2倍、2ビットなら4倍です。
0000 0011 = 3
0000 0110 = 6 ← 左に1ビット
0000 1100 = 12 ← 左に2ビット
ただし、固定ビット長では左端からあふれたビットは失われるので、常に数学的な意味で正確に2倍になるとは限りません。
右シフト
1ビット右にずらすと、2で割るイメージになります。
0000 1100 = 12
0000 0110 = 6 ← 右に1ビット
0000 0011 = 3 ← 右に2ビット
右端から押し出されたビットは失われます。
例えば 7 は、
0000 0111 = 7
↓ 右に1ビット
0000 0011 = 3
となります。
論理シフトと算術シフト
ここは科目Aでよく混同します。
| 種類 | 空いたビットの扱い | 主な考え方 |
|---|---|---|
| 論理シフト | 0を入れる | 符号なしのビット列 |
| 算術右シフト | 符号ビットを保つ | 符号付き整数 |
例えば8ビットで先頭が 1 の値を右へ1ビット動かすとします。
論理右シフト
1001 0000
↓
0100 1000
算術右シフト
1001 0000
↓
1100 1000
論理右シフトでは左に 0 が入り、算術右シフトでは負数の符号を保つため左に 1 が入ります。
論理 = 0で埋める、算術右 = 符号を保つ
と切り分けます。
算術右シフトでは、符号ビットも右へ動く?
はい。先頭のビットも含め、元のビット列全体が右へ動きます。 ただし、空いた左端には「元の符号ビットと同じ値」を新しく補います。元の先頭ビットをその場に固定するわけではありません。
次の例は、8ビットの2の補数表現で -48 を表したものです。
元の値 11010000 = -48
右へ1ビット 11101000 = -24
右へ2ビット 11110100 = -12
^^
左側には符号ビットの1を補う
例えば最初の1回では、もともと左端にあった 1 も1桁右へ動き、空いた左端を新しい1で埋めます。さらに右端の1ビットは捨てます。この動きを符号拡張(sign extension)と結び付けて理解するとよいでしょう。
算術右シフトで数値はどう変わるのでしょうか。2の補数で表した符号付き整数を1ビット算術右シフトすると、数値を2で割って負の無限大方向に丸めた結果になります。2ビットなら4で割ることに相当します。
-48 ÷ 2 = -24
-48 ÷ 4 = -12
割り切れない負数には注意します。例えば -5 は8ビットで 11111011 ですが、算術右シフト1ビットでは 11111101、つまり -3 です(-5 ÷ 2 = -2.5 を負の無限大方向に丸める)。
また、算術シフトは2の補数を作る操作ではありません。2の補数は「負数の表現方法」、算術右シフトは「符号付きの値を右へずらす操作」です。ビット列を符号なしの値として扱う場合やビットを取り出したい場合は論理右シフトを使うことがあります。負数表現の基本は2の補数で確認できます。
触って覚える:論理/算術でビット列と10進数はどう変わる?
見るポイント: 同じ8ビットから出発しても、左端を0で補うか、符号ビットで補うかによって、ビット列と数値の両方が変わります。まず 11010000 の1ビット右シフトを予想してから、方式を切り替えて確認しましょう。
この教材では、論理右シフトは8ビットの符号なし整数、算術右シフトは8ビットの2の補数整数として数値を解釈します。方式を切り替えると、元のビット列は同じでも10進数としての読み方が変わります。シフト数は0〜3ビットです。
方式と元の値を選び、右に動かすビット数を変えてみましょう。色の付いた左端のビットは、シフトによって新しく補われた部分です。
↓ 右にシフト
左端に補う値:1。-48 ÷ 2 = -24 → シフト後 -24。
16進数1桁は4ビット
16進数1桁は、2進数4ビットに対応します。
0₁₆ = 0000₂
A₁₆ = 1010₂
F₁₆ = 1111₂
そのため、
16進数1桁分ずらす
→ 4ビットシフト
16進数2桁分ずらす
→ 8ビットシフト
と考えられます。
一方、2ビットシフトのように16進数の桁境界と合わない場合は、2進数へ直して処理する方が安全です。
シフトと加算で掛け算を行う
2進数の乗算では、乗数のビットを下位から順に調べる方法があります。
乗数の最下位ビットを見る
↓
1なら現在の被乗数を結果へ加える
↓
被乗数を左シフト
乗数を右シフト
例えば 3 × 3 なら、
X = 3 = 0011 ← 被乗数
Y = 3 = 0011 ← 乗数
Z = 0 ← 結果
1回目はYの最下位ビットが 1 なので、
Z = Z + X = 3
Xを左シフト → 6
Yを右シフト → 1
2回目も最下位ビットが 1 なので、
Z = Z + X = 9
Xを左シフト → 12
Yを右シフト → 0
となり、結果は 9 です。
動かして確認:シフトと加算による乗算
乗数Yの第0ビットが1ならXをZに加算し、その後でXを左、Yを右に1ビットずつシフトします。次の例は16ビット符号なし整数の 3 × 3 です。
16ビットからあふれた上位ビットは捨てます。 Xは14回目に 49,152、15回目に 32,768、16回目に 0 になります。Yは2回目で0になるため、その後の加算はなく、Zは 9 のままです。
1ステップずつ確認:3 × 3
開始前(0 / 16回)
X(被乗数): Y(乗数): Z(結果):
Yの下位8ビット:00000011(右端が第0ビット)
「次へ」で第0ビットの判定から始めます。
確認ポイント:Xは左へ、Yは右へ1ビットシフトします。Xが2倍になるのは桁あふれがない間だけです。Yが0になった後も、16ビット分の処理として16回まで確認できます。
公式の出題範囲やシラバスは、IPA:基本情報技術者試験 から確認できます。
科目Aでどう出る?
科目Aでは、シフト後のビット列や16進数を求める問題が出ます。
まず、次の順番で判断します。
1. 左か右か
2. 何ビット動かすか
3. 論理か算術か
4. 空いたビットを何で埋めるか
5. 必要なら16進数へ戻す
特に「論理右シフト」なら、
右へずらす
+
左側を0で埋める
の2点をセットで確認します。
16進数のシフト問題は2進数に直す
例えば ABCD₁₆ を2ビット右へ論理シフトするとします。
A B C D
1010 1011 1100 1101
右に2ビットずらし、左を0で埋めます。
0010 1010 1111 0011
これを4ビットずつ16進数へ戻します。
0010 1010 1111 0011
2 A F 3
したがって結果は 2AF3₁₆ です。
試験中は、
16進 → 2進 → シフト → 16進
と処理すると、桁またぎのミスを減らせます。
16進数 AB88 を右へ2ビットずらす
16進数 AB88 を16ビットの符号なし整数として論理右シフトする例です。16進数の桁を直接動かすのではなく、4ビットずつ2進数に直します。
16進数 A B 8 8
2進数 1010 1011 1000 1000
↓ 論理右シフト2ビット
0010 1010 1110 0010
16進数 2 A E 2
答えは 2AE2₁₆ です。 右端の2ビットを捨て、左端には0を二つ補います。途中で16進数の区切りをまたぐことに注意してください。
動かして確認:0~4ビットの論理右シフト
下のボタンを押すと、AB88 の16ビットが右へ移動し、結果の16進数も変わります。見るポイント:4ビットの境界をまたいで、各桁がどう変化するか。
元の値:AB88₁₆(16ビット、論理右シフト)
元のビット列:1010 1011 1000 1000
移動後:0010 1010 1110 0010
16進数の結果:
左側の空きは0で埋め、右端からはみ出すビットは捨てます。
Pythonで確認するなら、hex(0xAB88 >> 2) の結果は '0x2ae2' です。なお、16ビット符号付き整数として算術右シフトする場合は別の結果になるため、試験では符号とシフトの種類を必ず確認します。
交互ビット列を足す問題
1010...10 のように1と0が交互に並ぶ値が出たら、次の順で確認します。
末尾が0
→ 2で割ると右へ1ビット
x = 1010...10
x / 2 = 0101...01
→ 1の位置が互い違い
足す
→ 1111...11
2nビット全部1
→ 2^(2n) - 1
選択肢問題なら、一般式を最後まで導く前に n = 1 や n = 2 を代入して候補を切る方法も使えます。ただし、理解するときは 「右シフトで1の位置が互い違いになり、足すと全部1になる」 ところまで押さえておくと、数字が変わっても対応できます。
シフトと加算を組み合わせて10倍を作る
正の整数 X を10倍にする操作を選ぶ問題では、シフトをすべて倍率に置き換えて、最後まで式を追うと判断できます(桁あふれは起こらないものとします)。
1ビット左シフト → ×2
2ビット左シフト → ×4
3ビット左シフト → ×8
10倍は 8X + 2X でも作れますが、(4X + X) × 2 と考えることもできます。
方法1:8倍と2倍を足す
元の値を X とすると、左に3ビットシフトした値(8X)と、左に1ビットシフトした値(2X)を足せば10倍です。
10X = 8X + 2X
= (X << 3) + (X << 1)
例えば X = 5 の場合、8ビットで桁あふれせずに計算できます。
X 0000 0101 = 5
X << 3 0010 1000 = 40
X << 1 0000 1010 = 10
---------
加算 0011 0010 = 50
間違えやすい方向に注意: 8倍と2倍を作るのは左シフトです。右に3ビット・右に1ビットずらすと、整数の論理右シフトではそれぞれ8で割る方向・2で割る方向になり、10倍にはなりません。
方法2:4倍に元の値を足してから2倍する
こちらは途中の加算結果全体をさらに左シフトする方法です。
X
↓ 2ビット左シフト
4X
↓ 元のXを加える
4X + X = 5X
↓ さらに1ビット左シフト
(5X) × 2 = 10X
大切なのは、最後の左シフトは「加算後の値全体」に掛かることです。途中の 4X + X で計算を止めないようにします。
次の4つの操作を倍率に直して比較してみましょう。
| 操作 | 式に直す | 最終的な倍率 |
|---|---|---|
| 3ビット左シフトした値と2ビット左シフトした値を加算 | 8X + 4X |
12倍 |
| 2ビット左シフトした値にXを加算し、さらに1ビット左シフト | (4X + X) × 2 |
10倍 |
| 3ビット左シフトした値にXを加算し、さらに1ビット左シフト | (8X + X) × 2 |
18倍 |
| 2ビット左シフトした値にXを加算し、さらに2ビット左シフト | (4X + X) × 4 |
20倍 |
迷ったらX=1で確認する
選択肢を式にしたあと、X = 1 を代入すると確認しやすくなります。
(4 × 1 + 1) × 2
= 5 × 2
= 10
ただし、最初からX=1だけで考えるのではなく、操作がどの値に掛かるかを式で確認するのが基本です。「さらにシフトする」とあれば、その直前の計算結果全体を動かします。
倍率を問う問題
| 問題文の表現 | 判断 |
|---|---|
| 左に1ビット | 2倍方向 |
| 左に2ビット | 4倍方向 |
| 左に3ビット | 8倍方向 |
| 右に1ビット | 2で割る方向 |
| 右に2ビット | 4で割る方向 |
| 右に3ビット | 8で割る方向 |
| 16進数1桁分を移動 | 4ビット |
ビット取り出し問題
1. 今の下位ビットを取り出す
→ ANDでマスク
2. 次に見るビットを下位へ持ってくる
→ 右シフト
乗算アルゴリズムでは、
乗数の最下位ビットを見る
被乗数は左シフト
乗数は右シフト
と整理します。
科目Bでどう使う?
科目Bでは、<< や >> のような演算子が使われることがあります。
x << 1
→ xを左に1ビットシフト
x >> 1
→ xを右に1ビットシフト
例えば x = 6 なら、
6 = 0000 0110
x << 1
→ 0000 1100 = 12
x >> 1
→ 0000 0011 = 3
となります。
ただし、実際のプログラミング言語では符号付き整数の右シフトの仕様が関係することがあります。試験問題では、問題文に「論理シフト」「算術シフト」「符号なし」などの指定があるかを先に確認します。
複数ビットをまとまりとして処理するときは、
下位4ビットを使う
↓
右に4ビットシフト
↓
次の4ビットを下位へ持ってくる
と読みます。
スタックへ取り出した値を順番に格納する処理では、スタック vs キュー の追加・取出し順序と合わせて読むと処理を追いやすくなります。
よくある誤解・混同
❌ 右シフトなら必ず左を0で埋める
必ずではありません。
論理右シフト
→ 0で埋める
算術右シフト
→ 符号を保つ
と区別します。
❌ 16進数を2ビット動かすなら、16進数の桁をそのままずらせばよい
16進数1桁は4ビットです。
2ビットシフトは16進数の桁境界をまたぐので、2進数へ直す方が安全です。
16進数1桁
= 4ビット
❌ 2ビット左シフトは2倍
2ビット左シフトは、倍率のイメージでは 2² = 4倍 です。
❌ 1010...10 + 0101...01 では桁上がりが起きる
この2つは、1が立っている位置が重なりません。
101010
010101
------
111111
各桁で 1 + 1 が発生しないため、桁上がりは起きません。
ここから 「2nビット全部1 → 2^(2n) - 1」 と判断できます。
❌ 右シフトで押し出されたビットも残る
固定ビット長では、右端から押し出されたビットは失われます。
❌ 右に4ビットシフトするのは、今の下位4ビットを保存するため
逆です。
今の下位4ビットを使い終えたあと、次の4ビットを右端へ持ってくるためにシフトします。
❌ 論理シフトと算術シフトは、どちらも同じ結果になる
先頭ビットが 1 の値を右シフトすると違いが出ます。
論理右
→ 0を入れる
算術右
→ 符号ビットを維持
まとめ(試験直前用)
- 左シフトは2倍方向、右シフトは半分方向
- シフトと加算が続く問題では、操作を最後まで式に直す(例:
(4X + X) × 2 = 10X) - 論理右シフトは左を0で埋める
- 算術右シフトは符号を保つ
- 16進数1桁は4ビット
1010...10を2で割ると0101...01になり、足すと 2nビット全部1 = 2^(2n) - 1- 16進数の2ビットシフトなど、桁境界と合わない問題は 16進 → 2進 → シフト → 16進 で処理する
- 右へ押し出されたビットは失われる
- ビット取り出しでは、ANDで取り出してから右シフトで次のビットを下位へ持ってくる
- 乗算では「乗数の最下位ビット・被乗数は左・乗数は右」を見る
試験中は、まず次の4点を確認します。
方向は?
何ビット?
論理か算術か?
空いた場所を何で埋める?