二進数の奇数の乗除算

解決済

質問者：RWSP
質問日時：2009/03/06 00:29
回答数：4件

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

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (4件)

ベストアンサー優先
最新から表示
回答順に表示

No.2ベストアンサー

回答者： tetsu_pati
回答日時：2009/03/06 01:12

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

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

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

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

- 0
- 件

通報する

この回答へのお礼

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

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

通報する

お礼日時：2009/03/06 19:26

No.4

回答者： tadys
回答日時：2009/03/06 11:15

シフトと加算で行います。

例えば　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となります。

- 0
- 件

通報する

この回答へのお礼

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

通報する

お礼日時：2009/03/06 19:22

No.3

回答者： siremono2496
回答日時：2009/03/06 06:40

結局のところ、一番近い2のべき乗までシフトして、過不足を引いたり足したりするしか方法はありません。

小さい数どうしの乗算の場合は、下手に考えるよりもループで1つずつ足していった方が速い場合だってありえます。

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