コンピューターが二進数を使って掛け算や割り算をするために必要なシフト演算についてを説明する。
シフト演算の仲間である論理シフトや算術シフトも実際の計算例を用いてわかりやすく説明する。
シフト演算とは
シフト演算とは、2進数のビット列を左や右にずらす操作のこと。
シフト演算によって、コンピューターで掛け算や割り算を行うことができる。
シフト演算の例
2進数でシフト演算を行なうときは、右に1桁シフトすると2倍され、左にシフトすると、1/2倍される。
例として110をシフト演算すると
- 右シフト：110→1100 (10進数だと6→12になるので2倍)
- 左シフト：110→11 (10進数だと6→3になるので1/2倍)
になる。
また、10進数でシフト演算を行なうときは、右に1桁シフトすると10倍され、左にシフトすると、1/10倍される。
例として250をシフト演算すると、
- 右シフト：250→2500 (10倍)
- 左シフト：250→25 (1/10倍)
となる。
論理シフトと算術シフト
このシフト演算の中には、論理シフトと算術シフトの二つがある。
- 論理シフト：符号を考慮しないでシフト演算を行う
- 算術シフト：符号を考慮してシフト演算を行う
符号とは、先頭のビットを0=正、1=負として扱うこと。
論理シフト
論理シフトは、符号を考慮しないで行うシフト演算であり、左論理シフトと右論理シフトがある。
左論理シフト
左論理シフトはビット列を左にずらす。
- 左に1つずらすと、2¹倍
- 左に2つずらすと、2²倍
という形で、ずらした分をnとすると、2ⁿ倍になるのが、左論理シフトとなる。
例えば、1000(10進数だと8)を左に二つシフトすると、100000(10進数だと32)となるが、8 × 2² = 32となのであっている。
順序としては、
- 左にシフト
- シフトした分左にはみ出た数字を削除
- シフトした分右に空いたスペースを0で埋める
という手順となる。
右論理シフト
右論理シフトはビット列を右にずらす。
- 右に1つずらすと、1/2¹倍
- 右に2つずらすと、1/2²倍
という形で、ずらした分をnとすると、1/2ⁿ倍になるのが、右論理シフトとなる。
例えば、1000(10進数だと8)を右に二つシフトすると、10(10進数だと2)となるが、8 × 1/2² = 2となので計算できていることが分かる。
順序としては、
- 右にシフト
- シフトした分右にはみ出た数字を削除
- シフトした分左に空いたスペースを0で埋める
という手順となる。
算術シフト
論理シフトと違い、算術シフトは、符号を考慮して行うシフト演算であり、左算術シフトと右算術シフトがある。
左算術シフト
算術シフトも論理シフトと同じく、ずらした分をnとすると、2ⁿ倍になるのは変わらない。
ただし、一番左の数字は符号ビットとして扱い、シフトをさせずに固定させる。
下に例を入れる。
一番左の1は符号ビットとして - として扱うため、11101000 (符号付き10進数で-24)を左に二つシフトすると、10100000(符号付き10進数で-96)となる。
-24 × 2² = -96となるため、計算できていることになる。
順序としては、
- 一番左の符号ビット1は固定
- その他の数字を左にシフト
- はみ出た数字を削除し、右側の空いたスペースを0で埋める
- 固定した符号ビットを合わせる
という手順となる。
オーバーフロー
もしはみ出た数字が符号ビットと異なる数字だった場合、オーバーフローといって、計算が合わなくなる。
例えば先ほどの例ではみ出た数字が1ではなく、0だった場合。
この場合、10001000(符号付き10進数で-120)から1010000(符号付き10進数で-96)となるため、計算が合わなくなる。
右算術シフト
右算術シフトも、基本はずらした分をnとすると、1/2ⁿ倍になる。
一番左の数字は符号ビットとして扱い、シフトをさせずに固定させる。
注意点としては、論理シフトや、左算術シフトは、空いたスペースを埋めていたが、右算術シフトに関しては、空いたスペースにビット符号を埋める。
もしビット符号が0であれば、空いたスペースに0を埋めるし、ビット符号が1であれば、空いたスペースには1を埋める。
一番左の1は符号ビットとして - として扱うため、10001000 (符号付き10進数で-120)を右に二つ算術シフトすると、11100010(符号付き10進数で-30)となる。
シフト演算による掛け算と割り算
シフト演算で掛け算や割り算を行うにはどのようにすれば良いだろうか。
シフト演算による掛け算
シフト演算による掛け算は、2ⁿの足し算に置き換えることで計算ができる。
例として13をかける時の手順を考える。
手順としては、
- 13を2ⁿで計算できる数に分ける (8と4と1に分解)
- それぞれをシフト演算
という流れとなる。
シフト演算による割り算
割り算の場合は、「元の数から何回数を引くことができるか」という引き算の考え方をすることで、計算できる。
例えば、「9 ÷ 3の場合は、9から3を何回引くことができるか」という考え方を用いる。
9と3を2進数に変換して計算する。
9 ÷ 3の手順としては
- 11の数字を1001を超えないように1ビットシフト (2ビットシフトだと1100になり、1001を超えてしまうので、1ビットだけシフトさせる)
- 引き算する
- 余りの11をまた11で引く
- 引き算を合計2回行い、最初の1回目の引き算では1ビットシフトさせて2回目の引き算では0回シフトさせたため、2¹ + 2⁰ を足し合わせる
- 答えの３が出る
という手順になる。
コンピュータの全体像
コンピュータの全体像を知ると、数学とコンピューターサイエンスの結びつき方もより深く理解できる。
こちらにコンピューターサイエンスの全体像についてまとめた。
-
-
Screen-Shot-2021-06-11-at-11.45.16
続きを見る
