C++で、b[bit]の非負整数(例えば、unsigned long)2つa0,a1を用いて、2b[bit]の非負整数を表現した場合の除算に関する質問です。
非負整数 a=a0*2^b+a0 を b[bit]の非負整数 D(≠0) で割った、商と余りを求めたいのですが、例えば次のように求めようとします、
d0 = a0/D.
m0 = a0%D.
d1 = (m0*2^b+a1)/D = (m0*2^b)/D + a1/D
m1 = (m0*2^b+a1)%D = (m0*2^b)%D + a1%D
ですが、ここで (m0*2^b)/D と (m0*2^b)%D をb[bit]の非負整数に対する演算のみ(ループ処理も含めたくない)を用いて計算する方法が思いつかないのですが、何か良い方法はありませんでしょうか?
上記が計算できれば、
商 d = d0*2^b + d1.
余り m = m1
と構成できます。
No.1ベストアンサー
- 回答日時:
まず、質問者さんの立てた式には、計算過程に誤りがあります。
d1 = (m0*2^b)/D + a1/D
m1 = (m0*2^b)%D + a1%D
この「/」が整数除算だとすると、この/・%では、正しい計算はできません。
(例えば、b=4bitで考えましょう。50=4*2^4+2ですが、これを7で割った場合、
(4*2^4)/7+2/7=48/7+2/7=6+0=6
(4*2^4)%7+2%7=48%7+2%7=6+2=8
つまり、50を7で割った商が6で余り8になってしまいます。
つまり、個別に出した商や余りを単純に足すことはできません。
さて、まず
a0をDで割った商をa0d、余りをa0m
a1をDで割った商をa1d、余りをa1m
2^bをDで割った商をbd、余りをbm
(a0*2^b+a1)をDで割った商を(d0*2^d+d1)、余りをm
とします。
このとき、元の数 a0、a1、2^bは、
a0 = a0d * D + a0m
a1 = a1d * D + a1m
2^b= bd * D + bm
という式が成り立ちますから、被除数 a0*2^b+a1 は、
(a0*2^b+a1) = (a0d * D + a0m)*2^b+(a1d * D + a1m)
= (a0d*2^b+a1d)*D + (a0m*2^b+a1m)
になります。ここで、右側の2^bに2^b= bd * D + bmを代入すると、
= (a0d*2^b+a1d)*D + (a0m*(bd*D+bm)+a1m)
= (a0d*2^b+a1d+a0m*bd)*D + (a0m*bm+a1m)
になります。
余りについては、
(a0d*2^b+a1d+a0m*bd)*D はDで割って余り0ですから、
m=(a0*2^b+a1)%D = (a0m*bm+a1m) % D
として求めることができます。
商については、
(a0*2^b+a1)/D = ((a0d*2^b+a1d+a0m*bd)*D + (a0m*bm+a1m))/D
= (a0d*2^b+a1d+a0m*bd)*D/D + (a0m*bm+a1m)/D
= (a0d*2^b+a1d+a0m*bd) + (a0m*bm+a1m)/D
になります。
つまり、基本としては、
d0=a0d
d1=a1d+a0m*bd+(a0m*bm+a1m)/D
a=(a0m*bm+a1m)%D
になります。
(ただし、この計算において、d1がb[bit]からオーバーフローする場合もありえます。
その場合をきちんと検査して、d1から適切な値を引いて適宜d0の方を足す、などとといった処理が必要です
また、a0m*bmがb[bit]からオーバーフローする場合もありえますので、そちらの検査も必要。
なお、
> 2^bをDで割った商をbd、余りをbm
については、そのままではb[bit]の演算では表現できませんが、
2^(b-1)をDで割った商をbd'、余りをbm'
とすると、
2^b=2^(b-1)*2 = (bd'*D+bm')*2
= 2*bd'*D+2*bm'
になりますから、
bd=2*bd'+(2*bm')/D
bm=(2*bm')%D
として、b[bit]の演算で求められます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(Microsoft Office) IF関数について教えてください 2 2022/05/10 13:31
- その他(プログラミング・Web制作) Visual Studio Code 関数の使い方について 3 2023/05/31 13:15
- Excel(エクセル) エクセルの関数に関しての質問です。 5 2022/10/07 11:17
- その他(教育・科学・学問) 小学生の算数の商について 3 2023/03/06 14:11
- Excel(エクセル) VBAで組み合わせ算出やCOUNTIFSの処理を高速化したいです。 4 2022/04/07 02:38
- 数学 環論の素元について 6 2022/05/09 04:04
- Excel(エクセル) ユーザー定義について質問です。 2 2023/06/28 13:21
- Excel(エクセル) エクセルを活用した受注表作成の中で関数・数式を教えてください。 3 2022/07/23 08:14
- Excel(エクセル) エクセルの関数式を教えてください。 2 2022/11/29 21:09
- Excel(エクセル) エクセル 関数について質問です。 2 2022/10/03 11:14
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
あああ..ああい..ああう とい...
-
エクセルを開いたらカウントし...
-
ある一定時間の最高値と最小値...
-
VBAマクロにての絶対値
-
セルに入ってる数式を他のセル...
-
エクセル インデックスを用い...
-
Excel 範囲指定スクショについ...
-
エクセルで特定の文字列が入っ...
-
ワイルドカード「*」を使うとう...
-
「段」と「行」の違いがよくわ...
-
EXCEL VBA 文中の書式ごと複写...
-
excelのデータで色つき行の抽出...
-
エクセルで複数のシートのクリ...
-
Excelで数字を入れたら対応する...
-
フォルダ内の全てのファイルに...
-
シートをコピーする下記記述で...
-
チェックボックスをクリックし...
-
B列の最終行までA列をオート...
-
VBA 指定した列にある日時デー...
-
エクセル マクロ オートフィ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
あああ..ああい..ああう とい...
-
VBAにて『元に戻すボタン』を作...
-
vbs 文字位置を中央に
-
select caseの入れ子
-
VBAバーコード照合 バーコード...
-
エクセルで選択したセルがディ...
-
指数関数近似を行うプログラム...
-
セルに入ってる数式を他のセル...
-
ある一定時間の最高値と最小値...
-
C++で、b[bit]の非負整数(例え...
-
xlookup関数の引数を利用して検...
-
スペース区切りのAND検索
-
エクセル インデックスを用い...
-
アセンブラでの記述について教...
-
VBAマクロ実行時エラーの修正に...
-
Worksheets メソッドは失敗しま...
-
マクロの「SaveAs」でエラーが...
-
エクセルで特定の文字列が入っ...
-
エクセルで離れた列を選択して...
-
B列の最終行までA列をオート...
おすすめ情報