【シフト演算③】シフト演算を使ったかけ算・割り算
今回はシフト演算を用いてかけ算と割り算を実現させる方法について解説していきたいと思います。
割り算は置いとくとして、かけ算はシフト演算が理解できていればすぐ出来てしまいます。まずは、かけ算からマスターしてしまいましょう。
その前に、シフト演算についてよく分からない！っていう方は以下のページで解説していますので参考にしてみてください！
https://www.sumappu.com/post-413/かけ算
2進数でかけ算を行うにはどうしたらいいのでしょうか？
2倍や4倍、8倍などの計算はシフト演算で実現できます。
でも、3倍・6倍・7倍といった2のn乗ではない乗数の場合、かけ算はどのように行うのでしょうか。
ここで必要なのが、数値の分解です。
例えばある数に7を掛けるとしましょう。7のままでは2のn乗で表すことはできませんが、分解すれば2のn乗を使って表すことができるのです。
どのようにするかと言いますと、、、
7を〇 + 〇という風に分解するのです。
7より小さい数で2の累乗数は何がありますか？2と4ですね。
ここで注意すべきなのが、できるだけ分解の作業を減らすために、できるだけ大きな数を見つけることです。2と4だと4の方が大きいので、
ですので、7を4と3に分解します。
続いて、3も同様に分解しましょう。3より小さい2は2の累乗数なので、3を2と1に分解できますね。
1は2の0乗なので、7を4と2と1に分解することで、2の累乗数の和で表すことができました。
ここまでの内容を踏まえると、ある数xを7倍する式は、以下のように表すことができます。
x ×7 = x ×(4 + 2 + 1) - ①
あとは、①式を変形していけばシフト演算と足し算のみで7倍の計算をできます。
x × (4 + 2 + 1) = (x × 4) + (x × 2) + x = (x × 2²) + (x × 2¹) + x
xを2ビット左シフトしたものとxを1ビット左シフトしたものとxを足すことで7倍の計算が行えることが分かりました。これが理解できれば、3倍も9倍も12倍も15倍もすべて計算できますね。
割り算
突然ですが、10÷5ってどういう意味でしょうか。
10を5分割したときにそれぞれの大きさはいくらでしょうか？という意味だと多くの人が解釈すると思います。
この考え方は間違っていませんし、むしろ正しいです。しかしこの言い方、以下のように言い換えができますよね？
10÷5は、10から5を2回引くことができることを表す。
10 – 5 = 5
5 – 5 = 0
ほら、2回引き算ができますよね？
これは30÷6や40÷8などすべての割り算に置いて言えることだと思います。
では、2進数での計算を考えていきましょう。
10÷5を2進数で考えます。10は2進数では1010です。5は101です。1010から101を何回引けるでしょうか。
1010 – 101 = 101
101 – 101 = 0
2回引くことができましたので、答えは2。2進数で表すのであれば10ですね。
ではもう少し大きい数を考えてみましょうか。30÷5はどうでしょうか。30は11110で5は101です。
1回1回引いていくのは面倒ですよね…人間は楽をしたい生き物なので、もっと楽に計算できる方法を考えましょう。
ここで出てくるのがシフト演算です。
101を、11110を超えない範囲で左シフトしてみましょう。101は3桁、11110は5桁なので2ビットまでシフト演算ができますね。なので2ビットシフト演算を行ってから引き算をすると…
11110 – 10100 = 1010
1010は101よりも大きい数なので、まだ引き算ができます。偶然にも先程1010 ÷ 101は行いましたね。答えは2でした。
しかし、シフト演算を使って計算をしてみましょう。1010は4桁、101は3桁なので、1ビット左シフトができますね。
1010 – 1010 = 0
引き算が終了しました。ここまで2ビットの左シフトと1ビットの左シフトを行いましたね。
したがって、2² + 2¹ = 6であるから、30÷5 = 6であることが分かりましたね。
例題
ある正の整数xに対して、"2ビット左シフトを行いxを加える"という操作を行うと、xの値は何倍になるか。ここで、オーバーフローは発生しないものとする。
ア.3 イ.4 ウ.5 エ.6
では実際に問題を解いてみましょう。
解説を始めるので、まだ回答を見たくない方はスクロールを止めてください。
2ビット左シフトを行うと、2² = 4 したがって4倍になります。xを加えるという操作ではシフト演算は発生しません。
4 + 1 = 5
したがって5倍になります。正答はウです。
まとめ
今回は、シフト演算を使ったかけ算と割り算について解説しました。
かけ算は、乗数を2の累乗数に分解して足し合わせることで、実現できます。
割り算は、シフト演算を用いた引き算を何回行ったかを求めることで答えを出すことができます。
今回の内容はそこまで難しくないのですが、説明をするのは難しかったです…（笑）。
この記事を読んでよく分からなくても、問題を解いていけばこの記事の内容を理解してもらえるのではないかと思っています。
というわけで、今回はここで終わりです。何か参考になる情報があれば嬉しいです。
最後までお読みいただき、ありがとうございました。