疑問
以下は応用情報の離散数学を勉強していたときの私の心中です
- 左論理シフトは空いたスペースに0を入れます→わかる
- 右論理シフトは空いたスペースに0を入れます→わかる
- 左算術シフトは空いたスペースに0を入れます→まあわかる
- 右算術シフトは空いたスペースを符号ビットで埋めます→いやなんで？？？？？
この疑問に答えてくれる記事が思ったより少なかったので、自分なりにたどり着いた結論と、それに納得できない人のための数式的な説明を書いた記事です。
論理シフト・算術シフトのやり方自体については記事がたくさんあるので、1つわかりやすそうなリンクを貼っておきます。
https://itmanabi.com/shift-operation/
たどり着いた結論
結論としては、算術シフトとは「2の補数表現の数を2倍したり1/2倍したときの挙動に名前をつけた」だけのものです。
なんともつまらない結論ですが、算術シフトが理解できなかったのは、ただ単に2の補数についての理解が足りていないだけ、というお話でした。
以下、2の補数についての具体的な計算をしてみた後、ではなんで2の補数はそのような挙動をするのか？という部分について数式的に掘り下げてみます。
2の補数の計算具体例
具体的に、8ビットの中で-28÷2=-14という演算を考えてみます。以下、2進数を$(n)_2$で表します。
まず、$28 = (00011100)_2$と表せます。この2の補数は、以下の2通りの方法で計算できます。
1. 定義どおりの方法
2の補数の定義は「足してちょうど位が1繰り上がった数になる数」でした。
今回の場合は8桁で考えているので、足してちょうど9桁の$(100000000)_2$になる数を考えたら良いわけです。
つまり逆に引き算をすればよく、答えは以下の通りになります。
(100000000)_2 - (00011100)_2 = (11100100)_2
2. 便利な計算方法
よく紹介されている計算が楽な方法です。$(00011100)_2$のビットをすべて反転させて1を足します。
反転させると$(11100011)_2$になるので、答えは以下のようになります。
(11100011)_2 + 1 = (11100100)_2
こっちの方法の方が圧倒的に楽ですね！普段の計算ではこちらを使用するのが良さそうですが、実は1番の方法も後で必要になってくるのでここで2通りの方法を紹介しました。
-28÷2=-14に戻る
以上の計算より、-28を2の補数表現で表すと$(11100100)_2$となります。
同様に、-14を2の補数表現で表すと$(11110010)_2$となります(計算略)
両者を見比べてみると、確かに「-28を右に1つシフトして、空いたスペースを符号ビット(今回は1)で埋めたもの」が-14になっていることが確認できます。
右算術シフトを理解できない場合は、まずはこの計算を手計算で追ってみて、実際に感覚をつかんでみるのが手っ取り早いというのが結論になります。
「え、ここまで長々書いておいて結論それだけ？」と思う方もいると思うので最後に数式的な説明をします。
全く厳密なものではないのでその点だけご了承ください。
右算術シフトの計算の数式的説明
以下、-28を右に1つシフトして、空いたスペースを符号ビット(今回は1)で埋めたものが-14になる理由を数式的に説明します。
まず、28の補数を$x$, 14の補数を$y$とします。$x, y$は28, 14を用いて次のように表せます。
ここで、先ほどの「1. 定義どおりの方法」を用いています。
x = (100000000)_2 - (00011100)_2 = 256 - 28
y = (100000000)_2 - (00001110)_2 = 256 - 14
ここで、28=14×2という関係を用いて28, 14を消去すると以下の関係式を得ます。
y = \dfrac{1}{2}x + 128 = \dfrac{1}{2}x + (10000000)_2
この数式の解釈は以下の通りです。
- 第一項$\dfrac{1}{2}x$は「右に1つシフトする操作」を表しています
- 第二項$(10000000)_2$は「空いたスペースを符号ビット(今回は1)で埋める操作」を表しています
この結果は、28と14でなくとも、8ビットでなく$n$ビットで考えたとしても一般に成り立ちます。
左算術シフトについてもやってみよう
「左算術シフトは空いたスペースに0を入れます」→これに関しても同様に説明できます。
8ビットの中での28×2=56という演算を例に説明してみます。
28の補数を$x$, 56の補数を$z$とします。$x, z$は28, 56を用いて次のように表せます。
x = (100000000)_2 - (00011100)_2 = 256 - 28
z = (100000000)_2 - (00011100)_2 = 256 - 56
56=28×2という関係を用いて28, 56を消去すると以下の関係式を得ます。
z = 2x - 256 = 2x - (100000000)_2
この式の解釈は以下の通りです。
- 第一項$2x$は、「左に1つシフトする操作」を表しています
- 第二項$-(100000000)_2$は、「左シフトによってはみ出た部分を捨てる操作」に対応します
上記の2操作のみしか行わないので、空いたスペースには0を入れる必要があります(+0をするとも言い換えられるかもしれません)。
この結果ももちろん一般に成り立ちます。
最後に
算術シフトなんてなかった。2の補数の計算をしっかりしよう。
あと数式はやっぱり偉大だった。