二進数の奇数の乗除算

質問

ＣＰＵの二進数の乗除算の計算で二進数は左にシフトしていけば
２倍、４倍、８倍と増えていくことはわかるのですが、
３倍、５倍、６倍、７倍のときはどのように計算しているのでしょうか？また
1/3倍、1/5倍、1/6倍、1/7倍のときはどのように計算しているのですか？
もし、的確なアルゴリズムがあるのならば教えてほしいですが、
わからなければ上の八通りだけでもいいです。
お願いします。

回答No.2

tetsu_pati · ベストアンサー

CPUでとのことでしたらハードウェアに乗算器、除算器というアーキテクチャがありますのでそれを活用するになると思います。

乗算器、除算器がない場合は乗数、除数の前提条件により
組むべきアルゴリズムが変わります。

乗数、除数が不定値のときは加算、減算で行います。
（例　５×３だと５を０に３回足す）
乗数、除数が固定値のときはビットシフト＋加算、減算で行います。
（例　５×３だと５を１回左シフトして５を足す）

以外とこうすれば効率がいいという方法はありません。

お礼

「意外とこうすれば効率がいいという方法はありません。」

そうなんですか。それを知れただけでとてもうれしいと思いました。
自分もそういうアルゴリズムだろうなとは思っていたんですが。
日々考えている方がいるのですかね。

回答No.4

tadys

シフトと加算で行います。
例えば　10x5　を計算する時はまずそれぞれを2進数で表しておいて
A=1010 B= 0101　K = AxB として
最初に
K = 00000000 とする。
sterp1:
　Bの最下位が1なので　K = K+A　= 00001010　とする。
　Aを左シフトして　A=10100
　Bを右シフトして　B=010
step2:
　Bの最下位が0なので　K はそのまま
　Aを左シフトして　A=101000
　Bを右シフトして　B=01
sterp3:
　Bの最下位が1なので　K = K+A　= 00110010　とする。
　Aを左シフトして　A=1010000
　Bを右シフトして　B=0
sterp4:
　Bの最下位が0なので　K はそのまま
かける数が4ビットなのでこれで計算の終わり。
答えは16進で0x32、10進では50となります。

お礼

ありがとうございます。
うむ～、ちょっとイメージしづらかったですね。
でもほかとの回答がやや違うような気がするので興味を持ちました。
ありがとうございます。

回答No.3

noname#194317

結局のところ、一番近い2のべき乗までシフトして、過不足を引いたり足したりするしか方法はありません。小さい数どうしの乗算の場合は、下手に考えるよりもループで1つずつ足していった方が速い場合だってありえます。

桁数が大きくなると、一番近い2のべき乗からでもけっこう遠くなるので、その場合は同様にまた一番近い2のべき乗を…という考え方になります。100倍だと、64+32+4などですね。数によっては、わざとオーバーさせて引いたり、端数調整を途中で行って最後に一回シフトする方が速くなる場合もあり得るので、そこには工夫の余地がありますけど、逆を言えばそれくらいしかアルゴリズムらしきものが介在するところはないと思います。

お礼

自分もそれくらいしか思いつきませんでした。
桁数が大きくなるにつれて難しくなりそうですね。
回答ありがとうございました。

回答No.1

SAYKA

大雑把に言うとだいたいこういう考え方

3a = a + a + a = 2a + a

お礼

回答ありがとうございました。