##シフト演算のしくみ
####10進数の桁移動
10進数の「$2020$」という4桁の数があったとします。
また、1の位から1万の位に当たる数を表現できる5つの枠があったとします。
| 桁数 | 5 | 4 | 3 | 2 | 1 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| | | 2 | 0 | 2 | 0 |
2020を左に1つずらし、空白の桁に$0$を追加したとき、この数は10倍され、5桁の数「$20200$」になります。
| 桁数 | 5 | 4 | 3 | 2 | 1 |大きさの変化|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|ずらす方向| ← | 2 | 0 | 2 | 0 | |
|ずらした数| 2 | 0 | 2 | 0 | 0 |10倍|
また、2020を右に1つずらし、枠からはみ出てしまった$0$を無視したとき、この数は1/10倍され、3桁の数「$202$」になります。
| 桁数 | 5 | 4 | 3 | 2 | 1 | 大きさの変化 | |
|---|---|---|---|---|---|---|---|
| ずらす方向 | 2 | 0 | 2 | 0 | → | ||
| ずらした数 | 2 | 0 | 2 | 1/10倍 |
このように、10進数のある数を左右に動かすことによって、その桁数や大きさを変化させることが出来ます。
####2進数の桁移動
2進数についても同様に、左右にずらすことで変化が起きます。
ここでは、「$01010$」という5桁の2進数について考えてみます。
また、2進数を表現できるビット数（桁数）の範囲を5とします。
$01010$を左に1桁ずらし、5ビットの範囲からはみ出した「$0$」を無視します。そして、新たに生じた空白の桁に「$0$」を加えたとき、この数は「$10100$」になります。
| 桁数 | | 5 | 4 | 3 | 2 | 1 |10進数の数 (大きさの変化)|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|ずらす方向| ← | 0 | 1 | 0 | 1 | 0 | 10 |
|ずらした数| ０ | 1 | 0 | 1 | 0 | ０ |20 (2倍)|
2進数$01010$は10進数では「$10$」になります。
そして、この数を右にずらして得られた5桁の2進数「$10100$」は10進数では「$20$」になります。
次に、$01010$を右に1桁ずらし、5ビットの範囲からはみ出てしまった$「0」$を無視します。そして、新たに生じた空白の桁に「$0$」を加えたとき、この数は3桁の2進数「$00101$」になります。
| 桁数 | 5 | 4 | 3 | 2 | 1 | |10進数の数 (大きさの変化)|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|ずらす方向| 0 | 1 | 0 | 1 | 0 | → | 10 |
|ずらした数| ０ | 0 | 1 | 0 | 1 | ０ | 5 （1/2倍） |
2進数「$00101$」は10進数では「$5$」になります。
##論理シフト
2進数と10進数の数をそれぞれ左右に動かしてみましたが、
このように、2進数の数列（ビット列）を左右に動かす操作のことをシフト演算と呼びます。
さらに、シフト演算において符号を考慮していないシフト演算のことを論理シフトと呼びます。
符号を考慮していないというのは、最上位のビットを符号ビットとせずにビット列全体をシフト演算させるということです。
そして、論理シフトを左右どちらに行うか、その方向に応じて左論理シフトと右論理シフトと呼び分けます。
####シフト演算と数値の変化
シフト演算によってその数の大きさが何倍されることになるのかは基数と桁の重みによって決まります。
したがって、先ほどのシフト演算の表のように、
10進数であれば、左にn桁だけずらした時（桁をn桁増やした時）に$10^n$倍され、
右にn桁だけずらした時（桁をn桁減らした時）に$10^{-n}$倍されるという事になります。
2進数であれば、左にn桁だけずらした時（桁をn桁増やした時）に$2^n$倍され、
右にn桁だけずらした時（桁をn桁減らした時）に$2^{-n}$倍されるという事になります。
####左論理シフトとオーバーフロー
これまでは、論理シフトにおいて「$0$」がはみ出てしまったときの操作を考えてきましたが、2進数の値によっては「$1$」が左右いずれかの桁からはみ出してしまう場合があります。
たとえば、5ビットの範囲を表示するという条件で、2進数5桁のビット列「$10011$」を1ビット分左論理シフトさせるとします。
| 桁数 | | 5 | 4 | 3 | 2 | 1 |10進数の数 (大きさの変化)|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|ずらす方向| ← | 1 | 0 | 0 | 1 | 1 | 19 |
|ずらした数| １ | 0 | 0 | 1 | 1 | ０ | 6？ |
この場合、これまでのように新しく出来た空白の1桁目に$0$を追加することに関しては問題ありませんでした。
しかし、今回はもともとあった5桁目の「$1$」が左論理シフトによってはみ出してしまいます。
ここで、左論理シフトを行う前と後のビット列に対応する10進数の値について注目してみます。
もともとの2進数5桁のビット列「$10011$」は10進数では「$19$」となります。
先ほどの「シフト演算と数値の変化」に基づくならば、左に1ビット論理シフトさせているので、論理シフト後の値は$2^1$倍されて「$38$」となるはずです。
しかし、はみ出してしまった「$1$」を消去した残りの5ビット「$00110$」は10進数で「$6$」であり、不適切な値になってしまいます。
一方で、はみ出してしまった「$1$」をビット列に含めた場合、6桁の2進数「$100110$」となり、この数を10進数に変換すると「$38$」になります。この値は左論理シフトで期待されていた結果です。
このことから、問題の原因は、左論理シフトでビット列からはみ出してした「$1$」を消去してしまったことにより、演算の結果が正しく表現できなくなってしまったことにあると言えます。
したがって、左論理シフトによって表現可能なビット数の範囲から「$1$」がはみ出してしまったとき、演算の結果を表示できる範囲を超えた状態になったという事になります。
この状態のことを「オーバーフロー」と呼びます。
####右論理シフトと余り
左論理シフトによるオーバーフローと同様に、右論理シフトによって「$1$」が右側にはみ出してしまうことがあります。
たとえば、5ビットの範囲を表示するという条件で、2進数5桁のビット列「$10011$」を1ビット分右論理シフトさせるとします。
| 桁数 | 5 | 4 | 3 | 2 | 1 | |10進数の数 (大きさの変化)|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|ずらす方向| 1 | 0 | 0 | 1 | 1 |→ | 19 |
|ずらした数| ０ | 1 | 0 | 0 | 1 | １ | 9？ |
この場合、これまでのように新しく出来た空白の5桁目に$0$を追加することに関しては問題ありませんでした。
しかし、今回はもともとあった1桁目の「$1$」が右論理シフトによってはみ出してしまいます。
ここで、右論理シフトを行う前と後のビット列に対応する10進数の値について着目します。
もともとの2進数5桁のビット列「$10011$」は10進数では「$19$」です。
先ほどの「シフト演算と数値の変化」に基づくならば、右に1ビット論理シフトさせているので、10進数で「$19$」に相当する2進数を$2^{-1}$倍するという演算になります。
そして、この演算は、「$19\div2$」という割り算に置き換えることが出来ます。
割り算の結果を整数と小数を使って表すならば、「9.5」という値になるはずです。
また、この演算結果を整数で表現するならば、「商と余り」という形式を用いて「$9$余り$1$」と表現されるはずです。
実際に、シフト操作後のビット列「$01001$」は10進数で「$9$」になります。そして、はみ出てしまった「$1$」はシフト操作後の値には含まれません。
だから、この演算において、シフト操作後のビット列は割り算の商を表します。
また、シフト操作によって5ビットの範囲からはみ出してしまった「$1$」は演算結果の余りを表現しているという事になります。
したがって、5ビットの整数範囲を表示するという条件で、2進数5桁のビット列「$10011$」を1ビット分右論理シフトさせると「$01001$」という値になり、その過程で「$1$」という余りが生じます。
【補足】右論理シフトと割り算との違いについて
| 桁数 | 5 | 4 | 3 | 2 | 1 | . | ||
|---|---|---|---|---|---|---|---|---|
| ずらす方向 | 1 | 0 | 0 | 5 | 0 | → | ||
| ずらした数 | 1 | 0 | 0 | . | 5 | 0 |
右論理シフトによって、「$50$」が整数5桁の範囲からはみ出てしまいました。
ここで、この表に小数点を置いていることに注目してください。
これまではシフト操作によってはみ出た部分については無視していましたが、「右にはみ出した数は小数部分であり、5桁では表現することが出来ない」ということを踏まえると、はみ出した「$50$」という数は小数であることが分かります。
したがって、「$10050$」を左論理シフトさせると整数部分では「$100$」と表現されますが、小数部分も含めると「$100.50$」という数になります。
シフト操作によって「$10050$」を単純にずらすと「$100.50$」という数が得られたわけですが、この演算に関して着目すると「$10050\times10^{-2}$」、つまり「$10050\div100$」をしていることになるわけです。
この演算を整数で割り切れる範囲で行うと、商は「$100$」、余りは「$50$」となります。
このときの商と余りは右論理シフトの整数部分と小数部分にそれぞれ一致しています。
シフト演算と割り算は表示形式こそ違っていますが、基数が10であり、シフト演算の桁移動数に応じた桁の重み($10^2=100$)と割り算における「除数($100$)」が一致しています。
そのため、シフト演算ではみ出してしまった小数部分である「$50$」と割り算の余りである「$50$」が一致します。
したがって、先ほどの2進数の右論理シフトではみ出してしまった「$1$」を2進数の小数部分「$0.1$」として扱い、論理シフト後の「$01001$」に加えた「$01001．1$」を10進数に基数変換すると、割り算の結果に等しい「$9.5$」という値になります。
##算術シフト
シフト演算において符号を考慮して行うシフト演算のことを算術シフトと呼びます。
算術シフトでは、最上位のビットを「$0$」(正)または「$1$」（負）の符号ビットとして扱い、それ以降のビットを左右にシフト操作します。
そのため、論理シフトに比べると、シフト操作ができる2進数の桁数が1つ減る事になります。
| シフト演算の種類 | シフト | 操 | 作 | で | き | る | 桁 | 数 | |
|---|---|---|---|---|---|---|---|---|---|
| 論理シフト | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| 算術シフト | 符号ビット | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
####左算術シフト
たとえば、「$11101000$」という8ビットの負の数を1ビット左算術シフトするとします。
このとき、最上位のビットを符号ビットとして扱うため、分かりやすく「①」としています。
| 桁数 | 符号ビット | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 10進数の値（大きさの変化） | |
|---|---|---|---|---|---|---|---|---|---|---|
| 動かす方向 | ← | ① | 1 | 1 | 0 | 1 | 0 | 0 | 0 | -24 |
| 動かした数 | ① | 1 | 0 | 1 | 0 | 0 | 0 | ０ | -48 (2倍) |
算術シフトでは、符号ビットは固定されるため、シフト操作はそれ以外の7桁に対して行われます。そして、シフト操作によって生じた空白の桁には論理シフトと同様に「$0$」を加えます。
ここで、元の数の7桁目の「$1$」に注目すると、左算術シフトによってはみ出してしまっていることが分かります。
左算術シフトでは左論理シフトとは異なり、左にはみ出た桁の値が符号ビットと同じであればオーバーフローを起こさないという性質があります。
そのため、今回の左算術シフトではみ出てしまった「$1$」は無視して良いという事になります。
こうして、「$11101000$」という8ビットの負の数を1ビット左算術シフトすると「$11010000$」という数になりました。
ここで、算術シフトの前と後のビット列の10進数の値に着目します。
「$11101000$」という8ビットの数は最上位の桁が符号ビットなので、残りの7ビットを10進数に変換します。また、残りの7ビットは「2進数の2の補数」で表現されているため、このことに注意して変換すると「$-24$」となります。
算術シフトにおいて、シフト演算による値の変化は論理シフトと同様です。
つまり、左にn桁だけずらした時（桁をn桁増やした時）に$2^n$倍され、
右にn桁だけずらした時（桁をn桁減らした時）に$2^{-n}$倍されるという事になります。
だから、10進数で「$-24$」になるビット列「$11101000$」を左に1ビット左算術シフトすると、10進数で「$-48$」となる8ビット列になるはずです。
実際に、左論理シフトによって得られた「$11010000$」を補数表現に注意して10進数に変換すると「$-48$」となっています。
したがって、「$11101000$」という8ビットの負の数を1ビット左算術シフトすると「$11010000$」という値になります。
####右算術シフト
「$11101000$」という8ビットの負の数を1ビット右算術シフトするとします。
このとき、最上位のビットを符号ビットとして扱うため、分かりやすく「①」としています。
| 桁数 | 符号ビット | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 10進数の値（大きさの変化） | |
|---|---|---|---|---|---|---|---|---|---|---|
| 動かす方向 | ① | 1 | 1 | 0 | 1 | 0 | 0 | 0 | → | -24 |
| 動かした数 | ① | ？ | 1 | 1 | 0 | 1 | 0 | 0 |
算術シフトでは、符号ビットは固定されるため、シフト操作はそれ以外の7桁に対して行われます。そして、シフト操作によって1ビット分の空白の桁が生じるわけですが、この桁を埋める際に注意が必要です。
先ほどの左論理シフトで、「左にはみ出た桁の値が符号ビットと同じであればオーバーフローを起こさない」という性質がありました。
このことから、論理シフトのようにこの空白の桁に符号ビットとは異なる「$0$」を入れてしまうと、左算術シフトした時にオーバーフローを起こしてしまいます。
だから、この空白の桁に入れるべき数字は符号ビットと同じ「$1$」になります。
もし仮に、符号ビットが正のビット列の右算術シフトを行うのであれば、同様に符号ビットと同じ「$0$」を入れます。
したがって、「$11101000$」という8ビットの負の数を1ビット右算術シフトすると10進数で「$-12$」を表す「$11110100$」という値になります。
| 桁数 | 符号ビット | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 10進数の値（大きさの変化） | |
|---|---|---|---|---|---|---|---|---|---|---|
| 動かす方向 | ① | 1 | 1 | 0 | 1 | 0 | 0 | 0 | → | -24 |
| 動かした数 | ① | ① | 1 | 1 | 0 | 1 | 0 | 0 | -12 （1/2倍） |
今回の例では出ませんでしたが、もし右算術シフトによって「$1$」が右にはみ出てしまった場合は、右論理シフトと同様に割り算の余りとなります。
##参考にさせて頂いた書籍
きたみりゅうじ 『キタミ式イラストIT塾 基本情報技術者平成31/01年』 技術評論社 2019年
##学習してみて
論理シフト・算術シフトの操作は覚えてしまえば簡単なのですが、1つ1つの操作の理由について考えてみるとなかなか深いなと感じました。これらの操作がビット列の掛け算・割り算の基礎となるそうなのできちんと理解しておきたいと思います。