- ベストアンサー
二進数の奇数の乗除算
ＣＰＵの二進数の乗除算の計算で二進数は左にシフトしていけば ２倍、４倍、８倍と増えていくことはわかるのですが、 ３倍、５倍、６倍、７倍のときはどのように計算しているのでしょうか？また 1/3倍、1/5倍、1/6倍、1/7倍のときはどのように計算しているのですか？ もし、的確なアルゴリズムがあるのならば教えてほしいですが、 わからなければ上の八通りだけでもいいです。 お願いします。
- RWSP
- お礼率93% (124/133)
- その他([技術者向] コンピューター)
- 回答数4
- ありがとう数5
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (3)
- tadys
- ベストアンサー率40% (856/2135)
シフトと加算で行います。 例えば 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となります。
お礼
ありがとうございます。 うむ～、ちょっとイメージしづらかったですね。 でもほかとの回答がやや違うような気がするので興味を持ちました。 ありがとうございます。
結局のところ、一番近い2のべき乗までシフトして、過不足を引いたり足したりするしか方法はありません。小さい数どうしの乗算の場合は、下手に考えるよりもループで1つずつ足していった方が速い場合だってありえます。 桁数が大きくなると、一番近い2のべき乗からでもけっこう遠くなるので、その場合は同様にまた一番近い2のべき乗を…という考え方になります。100倍だと、64+32+4などですね。数によっては、わざとオーバーさせて引いたり、端数調整を途中で行って最後に一回シフトする方が速くなる場合もあり得るので、そこには工夫の余地がありますけど、逆を言えばそれくらいしかアルゴリズムらしきものが介在するところはないと思います。
お礼
自分もそれくらいしか思いつきませんでした。 桁数が大きくなるにつれて難しくなりそうですね。 回答ありがとうございました。
- SAYKA
- ベストアンサー率34% (944/2776)
大雑把に言うとだいたいこういう考え方 3a = a + a + a = 2a + a
お礼
回答ありがとうございました。
関連するQ&A
- 2進数の加減乗除の仕組み
もし似たような質問がありましたら申し訳ありません。 色々と調べたのですが、混乱してわからなくなってしまい困っています。 (1)コンピュータが2進数で加減乗除を計算できる仕組みとはなんでしょうか？ (2)2進数の加減乗除の仕組みとは、具体的にはなんでしょうか？ (3)AND、OR、NOTの回路が演算回路なんでしょうか？ たくさん質問してしまいすみません。 皆様の回答お待ちしております。
- 締切済み
- その他（学問・教育）
- 加減乗除の素朴な疑問
こんばんは。 本当～にふと思った素朴な疑問です。 加減乗除の混じった計算式では、乗除を先にやれ！と小学校だか中学校だかで教わりましたが、 例えば ６÷３×２ という式の場合、記述順に計算していくと、解は４になりますが、先に乗法の３×２をやってしまうと、６÷６＝１と、違う結果になってしまいます。 電卓でやると４になりますが、このような式の場合は、記述してある順番通りに計算していくのが正しいのでしょうか？ くだらない質問で恐縮ですが、どなたか教えて頂けますと幸甚です。
- ベストアンサー
- 数学・算数
- [2進数 シフト演算 除算について]
[2進数 シフト演算 除算について] シフト演算について勉強中です。ご協力お願い出来たら幸いです。 乗算について例えば『1010』（符号ビットを考えず)を2倍 4倍 8倍（2のn乗）した場合 ビットを2倍であれば1つ、4倍であれば2つ・・・左に シフトすれば良いというのは理解しました。 また3倍 5倍などのケースも、 3倍であれば1ケタ左にシフトした数＋1010で求まる事も理解しました。 問題は除算です。他の質問を探ってみたのですが、考え方は一緒という回答で・・・詰まっています 除算は右シフトとの事ですが 先ほどの例である『1010』(10)ですがこれを1/2、つまり2で割ると 1つ右にシフトし1010→0101 となり 1010を1/4する場合右に2ビットシフトし 1010→0010.10 となり理解は出来ます。 しかし1/3 、1/5といった場合の計算の仕方が分かりません。 余りを出さないという考えで（近似値になると思いますが） 解き方をご教授願えたらと思います。
- 締切済み
- 数学・算数
- 2進数演算について
1. 6をBinary Codeal Decimalで表してください。 2. 51.16を2進数で表して、次に 1)IBM方式 2)IEEE方式 の、二つの方式で浮動小数点表示で表してください。 3. 51.16-61.15を2進数で表して、2's comp(2の補数表示)で演習してください。 4.-(20+ 6)×( 5+ 6) を、2進数表示で表して、Bocth's Algorithm で計算してください. 減算は2's comp部分積を右シフト。 5. (210+6)÷(15+6) 引き出し法で計算してください. 減算は2's comp部分剰余の左シフト。
- 締切済み
- その他（インターネット・Webサービス）
- 19年秋の問2について
問02 ２進数を３倍したもの 非負の２進数 b1b2…bn を３倍したものはどれか。 という問題で、２倍して元の値を足せば３倍というのは わかるのですが、 b1b2…bnを左に１ビットシフトすると b1b2…bn0というのが よくわかりません。 ｂｎ0ってなんなんでしょうか？？ もっと言ってしまうと、b1b2…bnという表現がそもそもよくわかりません。 左に１ビットシフト → ２倍 左に２ビットシフト → ４倍 左に３ビットシフト → ８倍 左に４ビットシフト → １６倍 右に１ビットシフト → １／２ 右に２ビットシフト → １／４ 右に３ビットシフト → １／８ 右に４ビットシフト → １／１６ というのは理解してるつもりなんですが、こういう形になると わけがわからないってことは本質的に理解できてないってことなんでしょうか？？
- 締切済み
- 情報処理技術者
- 素数の生成アルゴリズムについてです。
下記リンク内のアルゴリズムでは、多項式時間内に素数の生成が可能でしょうか。 なお、同スレ内には、他にも多々、素数生成アルゴリズムをコレクションしてありますので、出来ましたら、それらの時間計算量につきましても御教え下さい。 https://twitter.com/koitiluv1842/status/1500429851630931970
- ベストアンサー
- その他（プログラミング・開発）
- Pascalにて入力した式の演算
タイトルのとおり、Pascalにて入力した式の演算を行うプログラムを作ろうと考えています。 例えば 1 + 3 * 3 = と入力すると10と出力されるようなものです。 そこで、アルゴリズムとしては 式を全てcharとしてread 括弧があるか探し、あるなら括弧閉じるを探す 括弧内で乗除算を探す その右と左の数をintegerなりに変換して演算 以下同様に計算 …という風に考えました。 そこで質問なのですが、 式のreadをするとき、変数は配列型でいいのでしょうか 配列型だとひとつの配列に二桁以上の数ひとつだけ、という風にしか収納出来ないと思うので、これでは不可能な気もします。 また配列型では不可ならどうすればいいでしょうか。 次に、式をreadした後、そのreadをどのようにして終わらせるか 以上二点がよく分からないので、よろしければお答え願います。 また私の考えが大きく違う時等も御指示お願いします。
- ベストアンサー
- その他（プログラミング・開発）
- シフト演算の左シフトが何で72になるのでしょうか？
■やりたいこと ・100を左に1ビット(1けた)シフトさせたら2倍になることを確かめたい ■試したこと ・100を2進数へ変換 → 1100100 ・左に1ビット(1けた)シフト → 1001000 ・1001000を10進数へ変換 → 72 ■質問 ・どこで間違えているのでしょうか？
- ベストアンサー
- 情報処理技術者
- サイコロの目の奇数・偶数問題です。
開始の数を1として、1回目サイコロを振り奇数が出ると2倍して1たす。偶数がでると2倍する。例えばサイコロの目が1回目奇数の時3になり偶数の時2になる。3回、サイコロを振って奇数奇数偶数がでると14になる。そういう試技を8回行い奇数が3回偶数が5回でるとすると最後の数は56通り考えられますが総和はいくらになりますか？ノートに書いてやってみましたが19691ですが、簡単な計算と考え方を教えてください。
- ベストアンサー
- 数学・算数
- 10進数 → 2進数
小数点を含んだ実数の、10進数から2進数への変換のやり方がよくわかりません。できるときとできないときがあります。たとえば、 (0.1)_10 = (0.0001100110011・・・)_2 ※(A)_xとは、数値Aのx進数表現というイミです。以下もこの表現を使います。 となるらしいですが、どうやればいいのでしょうか？わかりません。 また、ついでに聞いておきたいことがもう一つあります。小数点を含まない数値の 変換も教えていただきたいです。 たとえば今までぼくは、(101)_10を2進数に変換するのに、 (101)_10 = (100 + 1)_10 = ( 2^2・25 + 1 )_10 = ( 2^2・( 2^3・(2 + 1) + 1 ) +1 )_10 = (2^6 + 2^5 + 2^2 + 2^0 )_10 = (1100101)_2 などという、めんどくさいことをやっていたのですが、もっとスマートなやりかたはないでしょうか？ コンピュータもいちいちこんなやり方でやっていたら、計算量多すぎてやってられないような気がするので、きっとあると思うんですけど…簡潔なアルゴリズム…
- ベストアンサー
- 数学・算数
お礼
「意外とこうすれば効率がいいという方法はありません。」 そうなんですか。それを知れただけでとてもうれしいと思いました。 自分もそういうアルゴリズムだろうなとは思っていたんですが。 日々考えている方がいるのですかね。