【シフト演算】2進数の掛け算・割り算のやり方

10進数では、数字の桁を左にずらすと10倍、右にずらすと1/10になります。

例えば、250という数字があるとすれば、

• 左にずらす：2500（10倍）
• 右にずらす：25（1/10）

2進数の場合、数字の桁を左にずらすと2倍、右にずらすと1/2になります。

例えば、1100（10進数だと12）

• 左にずらす：11000（10進数だと24、つまり2倍）
• 右にずらす：110（10進数だと6、つまり1/2）

このように数字を左や右にずらすだけで、（2進数なら）2倍や1/2の計算は簡単にできます。これを『シフト演算』と言います。

では2進数で2倍や1/2以外の掛け算や割り算（例えば3倍とか5で割るとか）を計算するにはどうしたらよいでしょうか。

2進数の掛け算のやり方

10進数での「5×7」を2進数のシフト演算でやってみましょう。

まずは5と7を2進数で表してみます。

• 5→0101
• 7→0111

そして、7という数字を2の乗数で分解すると以下のようになります。

• 2²+2¹+2⁰

2の乗数をシフトした数字をそれぞれに掛ければ、2進数で5×7ができます。

• 5×2²+5×2¹+5×2⁰
• =0101を左に2回シフト+0101を左に1回シフト+0101を左に0回シフト
• =10100+1010+101
• =100011

100011は10進数だと35なので、計算合ってますね。

2進数の割り算のやり方

割り切れる数字

10進数の9÷3を2進数のシフト演算でやってみましょう。

• 9は2進数で1001
• 3は2進数で0011

まずは3を左にシフトします。ただし9を超えない範囲で。

• 左に2回シフト：1100→12なので9を超えてしまう…
• 左に1回シフト：0110→6なのでOK

左に1回シフトした数字を9から引き算します。

• 1001 - 0110 = 11

今度は11（10進数だと3）を再び3を左にシフトした数字で引き算します。

• 左に1回シフト：110→9なので3を超えてしまう…
• 左に0回シフト：11→3なのでOK

11から11を引きます。

• 0011 - 0011 = 0

左に1回シフト（2¹）と左に0回シフト（2⁰）を引くことができたので、答えは11となります。

11は10進数で3なので、合っていますね。

余りが出る数字

では次に10進数の8÷3を2進数のシフト演算でやってみましょう。

• 8は2進数で1000
• 3は2進数で0011

同じくまずは3を左にシフトします。ただし8を超えない範囲で。

• 左に2回シフト：1100→12なので8を超えてしまう…
• 左に1回シフト：0110→8なのでOK

左に1回シフトした数字を8から引き算します。

• 1000 - 0110 = 10

10は11で割れないのでここで計算終了です。

左に1回シフト（2¹）で引くことが出来たので、答えは10、余り10。

10は10進数で2なので、8÷3の答えは2余り2ということで、合っていますね。

論理シフトと算術シフト

ちなみに、シフトの仕方には2種類あります。

論理シフト

8ビットの2進数が合った場合、先頭の数字も含めて単純に左右にシフトするやり方を『論理シフト』といいます。

左にシフト（2ⁿの掛け算）

例えば以下のような2進数があった場合、

• 00101100（10進数だと44）

左に2桁論理シフトをすると以下のようになります。

• 10110000（10進数だと176）※右側は0を増やす

44の2²倍は176なので、左にn回シフトするごとに2ⁿ倍となります。

ただし、左にシフトするときに1が含まれていた場合変な数字になってしまいます。この現象を『オーバーフロー』といいます。

例えば、

• 11001100

という数字を左に2桁論理シフトすると、

• 00110000

と先頭の11が抜けてしまい変な数字になってしまう。

右にシフト（1/2ⁿの割り算）

例えば以下のような2進数があった場合、

• 00111100（10進数だと60）

右に2桁論理シフトすると、

• 00001111（10進数だと15）※左側は0で埋める

60÷2²は15なので合っていますね。

ただし、右にシフトして1がはみ出た場合は、オーバーフローではなく余りです。

例えば右に3桁論理シフトすると、

• 00000111.1

111で余りは0.1。10進数だと7.5になっているので、合っています。

算術シフト

先頭の数字1桁（符号を表す"符号ビット"）を残して左右にシフトするやり方を『算術シフト』といいます。

左にシフト（2ⁿの掛け算）

例えば、

• 11100100（10進数だと-28）

を左に2回算術シフトすると、

• 10010000 （10進数だと-112）※先頭の1は残す、右側は0で埋める

になります。

-28×4は-112なので合っています。

※先頭行が1で負の数である場合は補数。

オーバーフロー

左に算術シフトする場合、先頭の数字と異なる数字がはみ出るとオーバーフローを起こします。

例えば、

• 10011100
• 01101011

などの左にシフトする場合。

右にシフト（1/2ⁿの割り算）

今度は右に算術シフトしてみましょう。

• 11100100（10進数だと-28）

という2進数があった場合、右に2桁シフトすると、

• 11111001 （10進数だと-7）※先頭の数字は残す、算術シフトの場合は右にシフトするとき符号ビットと同じ数字を追加する点に注意

-28 / 4 = -7なので計算合っています。

右にシフトしてはみ出た数字は、論理シフトと同じく余り扱いとなります。

おわりに

割り算がめんどくさいので筆算でやったほうが早そうです。