No.16ベストアンサー
- 回答日時:
ANo.15 は「引き戻し法」ですね。
いわゆる普通の「割り算の筆算」をそのまま2進数ベースで実装したものです。(10進の割り算の場合は、各桁で「1倍~9倍のどこまで引けるか」を計算しますが、2進数なので、「引ける(その桁は1)か引けない(その桁は0)か」の2択の判定になります。
それをもうちょっと進めた(計算量を減らした)方法に「引き放し法」というのもあります。「引けるかどうか」チェックしてから「引く」のは二度手間なので、「引いてしまってから、結果によって次の処理を変える(負になったら、次のステップでは足すようにする)」というものです。
でも、この手の処理は「CPUの内部でハードウェアで実装されている」機能ですから、それをソフトウェアで実装するのは遅いだけでメリットはありません。
多倍長演算が例に挙げられてますけど、多倍長の2進数で実装する場合でも、
個々の演算は通常の加減乗除の組合せで実装するのが普通です。
例えば、32bitCPUで256bitの数値演算をしたいのであれば、
「4294967296進数で8桁の数値」を扱うようにすればいいんです。
簡単な例ですが、以下、64bitの数値を16bit×4桁と考えて10で割るコードです。除数の方も多倍長になるとやることは格段に複雑になりますが、演算の基本方針は同じです。
#include <stdio.h>
int main(int argc, char *argv[])
{
union {
unsigned long long ulonglong;
unsigned short ushort[4];
} x, y;
unsigned int div, mod;
x.ulonglong = 9876543210LL;
printf("%lld = %d * (1<<48) + %d * (1<<32) + %d * (1<<16) + %d\n", x.ulonglong, x.ushort[3], x.ushort[2], x.ushort[1], x.ushort[0]);
/* x86 CPUは Little Endian なので、ushort[3]が上位でushort[0]が下位 */
div = x.ushort[3] / 10;
mod = x.ushort[3] % 10;
y.ushort[3] = div;
div = (mod * 65536 + x.ushort[2]) / 10;
mod = (mod * 65536 + x.ushort[2]) % 10;
y.ushort[2] = div;
div = (mod * 65536 + x.ushort[1]) / 10;
mod = (mod * 65536 + x.ushort[1]) % 10;
y.ushort[1] = div;
div = (mod * 65536 + x.ushort[0]) / 10;
mod = (mod * 65536 + x.ushort[0]) % 10;
y.ushort[0] = div;
printf("%lld / 10 = %lld mod %d\n", x.ulonglong, y.ulonglong, mod);
}
回答ありがとうございます。
「引き戻し法」「引き放し法」覚えておきます。
>多倍長演算が例に挙げられてますけど、多倍長の2進数で実装する場合でも、
>個々の演算は通常の加減乗除の組合せで実装するのが普通です。
なるほど、私は初めから多倍長演算になると普通の乗除算は使えないと勝手に考えてしまい、このような質問をすることになっていました。
このような考え方があったのですね。
教えていただき、ありがとうございました。
No.15
- 回答日時:
int n; //被数
int div; //割る数
int anser = 0;// 答え
int i;
for(i = 31; i >= 0; i-- )
if( n >> i >= div)
{
i+= i;
n-= div<<i;
}
こんなんでどうですか
負数?64bit?
いやそんなの知りません
回答ありがとうございます。
ずいぶん簡潔なコードですね。
なかなか興味深いです。
負数なんかは、どんなアルゴリズムでも適当に処理できると思ってます。
ただ、複雑にするのは望んでは降りませんので、特に必要ではありません。
さまざまな回答を頂いておりまことに感謝いたしております。
ありがとうございました。
No.14
- 回答日時:
負数には、対応していない。
int div10(int x)
{
int y = ((((x>>3)+x)>>1)+x)>>4;
int t;
do{
t = x-(((y<<2)+y)<<1)+1;
y += ((((t>>3)+t)>>1)+t)>>4;
}
while(t > 10);
return y;
}
回答ありがとうございます。
一応プログラム動かして確認してみました。
どういったアルゴリズムなのかちょっと理解できていませんが
じっくり考える前にお礼を言わせて頂きます。
ありがとうございました。
No.13
- 回答日時:
基本的には引き算に展開することになると思います。
ただ、そのまま引いたのでは確かに回数が多くなりますので、適当にシフトを使います。
例えば、123456÷10を計算する場合、
最上位の値1をまず10で割ります。
1÷10=0余り1
この余りと次の位を合わせた数を10で割ります。
12÷10=1余り2
これを繰り返します。
23÷10=2余り3
34÷10=3余り4
45÷10=4余り5
56÷10=5余り6
結果、12345余り6と求まります。
これは10進数で行いましたが、2進数でも16進数でも原理は一緒です。多倍長整数や、固定小数点にも応用できるでしょう。浮動小数点にも、もう一ひねりすれば使えるはず。
回答ありがとうございます。
間違っていたらすみません。これも復元法でいいのでしょうか?
昨日ですけれども、「復元法」を教えていただいてそのように理解しています。
これだと、6回のループ(桁数分)で終わりますね。
もっと長い数値に適応しても大丈夫な気がします。
分かりやすい解説感謝いたします。
No.12
- 回答日時:
kenji_akiさん、はじめまして。
本来のご要望である、除算を使わずに10で割る方法については、すみませんが判りませんので、
>多倍長のバイナリ16進数から10進数に変換する方法だけでもいいです。
>たぶん、そのほうが手っ取り早いです。
の部分だけについてですが、サンプルを作成しましたので宜しければ検討してみて下さい。
このサンプルは、指定したバイト長の「16進値→10進値変換」を行うものです。
検証用に、その逆変換「10進値→16進値変換」の処理も入れてあります。
※Windows98SE+Visual C++ 5.0の環境で作成しました。
ただ、このサンプルでは整数値に変換しているため、64bit整数値での範囲が限界となります。
あと、すみませんが「ループ処理」が入っています。(※これはどうしても外せません!)
※的外れかもしれませんが、参考になれば幸いです。m(__)m
■サンプルソース
/*
* hex64.cpp:nバイト長16進値←→10進値相互変換
* ・指定バイト長の16進値と10進値の相互変換を行う。
* ・本サンプルでは、8バイト長(_int64)の16進値を取扱う。
*/
#include <stdio.h>
#include <stdlib.h>
/*
* Function: main
*/
int main()
{
unsigned char H1[8]; /* 変換元の16進値用(64bit) */
unsigned char H2[8]; /* 変換先の16進値用(64bit) */
__int64 ll_d1; /* 変換先の10進値用(64bit整数) */
__int64 ll_d2; /* 変換元の10進値用(64bit整数) */
int i, n;
/* 変換元16進値セット */
H1[0] = 0xef;
H1[1] = 0xcd;
H1[2] = 0xab;
H1[3] = 0x89;
H1[4] = 0x67;
H1[5] = 0x45;
H1[6] = 0x23;
H1[7] = 0x01;
/* 16進値のバイト数セット */
n=8;
/* 16進値→10進値変換(変換途中のデータ表示付き) */
ll_d1=0;
for(i=n-1;i>=0;i--){
ll_d1<<=8; ll_d1+=H1[i];
printf("ll_d1=%20I64d = [0x%016I64x]\n", ll_d1, ll_d1);
}
/* 10進値→16進値変換(検証用に逆変換する) */
ll_d2=ll_d1;
for(i=0;i<n;i++){
H2[i]=(unsigned char)(ll_d2&0xff); ll_d2>>=8;
}
/* 16進値の内容ダンプ */
printf("H1[x]=");
for(i=0;i<n;i++){ printf("0x%02x%s", H1[i], ((i<n-1)? ", ":"\n")); }
printf("H2[x]=");
for(i=0;i<n;i++){ printf("0x%02x%s", H2[i], ((i<n-1)? ", ":"\n")); }
return 0;
}
<実行例>
**>hex64
ll_d1= 1 = [0x0000000000000001]
ll_d1= 291 = [0x0000000000000123]
ll_d1= 74565 = [0x0000000000012345]
ll_d1= 19088743 = [0x0000000001234567]
ll_d1= 4886718345 = [0x0000000123456789]
ll_d1= 1250999896491 = [0x00000123456789ab]
ll_d1= 320255973501901 = [0x000123456789abcd]
ll_d1= 81985529216486895 = [0x0123456789abcdef]
H1[x]=0xef, 0xcd, 0xab, 0x89, 0x67, 0x45, 0x23, 0x01
H2[x]=0xef, 0xcd, 0xab, 0x89, 0x67, 0x45, 0x23, 0x01
回答ありがとうございます。
64ビットが限界ですか。
惜しいです。出来れば多倍長に拡張したいです。
それとも、やはり10で割りながら余りを数えていくしかないですかね。
コードまで記載して頂ありがとうございました。
No.11
- 回答日時:
整数ということですので、32bit整数に限ります。
ループなしで10で割るなら、1/10を掛けるというのが一つの方法です。
ただそのままでは1/10は整数になりませんので、定数として2^32/10を用意してこれを掛けます。
アセンブラなら32bit×32bit->64bitの乗算命令を、Cならunsigned long longの乗算を使って、被除数xと2^32/10の掛け算を行い、上位32bitを取れば10で割ったことになります。
32bit整数では2^32/10を厳密には表現できませんので、これも近似計算ではありますが、かなり精度良く計算できるはずです。
回答ありがとうございます。
出来れば、多倍長整数に対応したいと考えております。
目的としては16進から10進への変換等です。
どれだけのバイト数でどれだけの精度が出せるかが問題ですね。
参考にさせていただきます。ありがとうございました。
No.10
- 回答日時:
No.8です。
もはや本筋ではお役に立てそうもなく、スレ汚しになってしまいますが・・・。
>私が「除外させて下さい」と書いた10で引き続けてカウントする方法
>のほうが全然分かりやすくて単純だと思うのですが、
>なにか、問題があって使われないのでしょうか?
鋭いご指摘ですね。私も思わず一瞬、「アレ?何がいいんだっけ?」と思ってしまいました。
違いは、「ループ回数」です。
10引き続けてカウント方法だと、被除数の値/10回のループが発生するのに対して、私が提示した方法では、ビット数回分のループで計算が終了します。
被除数が100や1000くらいのうちは良いですが、1億とかになってくると計算時間に随分と差が出てきます。
・・・とは言え、いまどきのPCでは全く問題にならないのでしょうね・・・。
私も勉強になります。
回答ありがとうございます。
やはり、ループの回数ですか。
多倍長の除算に拡張したいと思っている身としては
大きな問題になります。
そう思うと、復元法なんかはずいぶん魅力的な方法に見えますね。
疑問にお答えくださって、ありがとうございました。
No.9
- 回答日時:
No.3です。
除数が10固定だけど小数点以下もあり‥‥難しいなぁ。被除数が整数で良くて余りを出していいのならNo.2さんのアルゴリズムを除算に置き換えればいいんだけど。それじゃダメらしいし。
とりあえず除算アルゴリズムにはいろいろあって紹介しきれないので、Googleしておきます。ただ、ループなしってのは私の知る限りでは無いですね。除数を10固定にしてうまく応用できれば、あるいは‥‥?
http://www.google.co.jp/search?hl=ja&suggon=0&q= …
回答ありがとうございます。
申し訳ありません。
小数点以下は切捨てで大丈夫です。
整数による10での除算です。言葉足らずで申し訳ありません。反省してます。
ANo.2さんの回答にあった乗算のアルゴリズムを除算に置き換えた場合。
近似値しか求まりませんでした。
誤差修正に必死になりましたが200弱の被除数においてしか正答は求まりませんでした。
unsigned int Decimation(unsigned int num)
{
unsigned int x;
num += num >> 1;
x = num;
while (num) {
x += num >> 4;
num >>= 4;
}
/*
ここで適当に足したり引いたりして誤差修正
if(x & 0xfff) x+=2;
桁数によって足す数を変えてみたりしたのですがうまくいきません。
誤差が出る法則性を見つけようにも自分の頭ではどうにも・・・
*/
x >>= 4;
return x;
}
やはり、ループなしでは無理ですか。
自分でもいろいろやっているのですが、自力ではどうにもならないですね。
参考にさせていただきます。ありがとうございました。
No.8
- 回答日時:
有名ドコロですが筆算方式はどうでしょう。
/10限定で極限のスマート計算法を求めておられるのでしたら、ちょっと違うのですが。。。
・関数仕様
a/bを求めます。
関数内で、aが商、modが剰余となります。
aは返りますがmodは散ります(笑)
#define BITWIDTH 32
int sftdiv(unsigned int a, unsigned int b)
{
int lop;
unsigned int mod;
mod = 0;
for(lop = 0; lop < BITWIDTH; lop++){
mod <<= 1;
if(a & (1<<(BITWIDTH-1)))
mod |= 0x01;
a <<= 1;
if(mod >= b){
mod -= b;
a |= 0x01;
}
}
return a;
}
回答ありがとうございます。
>/10限定で極限のスマート計算法を求めておられるのでしたら
その通りです。もう、10だけで割れれば十分だと思っています。
制限をかけてしまえば、単純化できるのではないかと。
これがANo.3さんの言っていた復元法と言うものでしょうか。
こうして、コードにしてみるとなるほど、という感じですね。
私が「除外させて下さい」と書いた10で引き続けてカウントする方法
int div(unsigned int a, unsigned int b)//b=10として
{
unsigned int answer, mod;
for (answer=0 ;a >= b; a-=b) {
answer++;
}
mod = a;
return answer;
}
のほうが全然分かりやすくて単純だと思うのですが、
なにか、問題があって使われないのでしょうか?
ちょっと納得できないでいます。
しかしながら、とても参考になりました。
コードまで貼って頂きありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(お金・保険・資産運用) 至急!【Wolt】各メニューの価格設定の簡単な計算方法 3 2023/03/05 11:58
- 電気工事士 6.6kVケーブル単芯325sq-1.5kmの遮蔽銅テープ抵抗値は何Ω? 1 2023/05/02 21:06
- 所得税 所得税の計算方法がわかりません 4 2022/06/26 13:36
- 減税・節税 国保➡社会保険に加入のがふるさと納税の恩恵がある? 3 2023/05/26 11:48
- 減税・節税 ふるさと納税返礼品制度を活用する為の方法 1 2023/05/23 15:56
- 統計学 標準誤差の求め方 2 2022/07/04 19:59
- その他(IT・Webサービス) 2点の住所を入力して直線距離を算出する方法・サイト 1 2023/02/22 16:52
- 消費税 インボイス制度 2 2022/11/19 14:44
- C言語・C++・C# 【CASLプログラム】 定数(80と55)を確保し、その和をGR1に、その差をGR2に求めるCASL 1 2022/12/16 01:17
- FX・外国為替取引 IRR(内部収益率)の求め方 1 2022/10/16 14:45
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
16進数 加算 減算 C言語
-
C言語プログラミングにて、arct...
-
VB6.0での小数点の扱いについて
-
O(n log n)について2
-
VB6のFIX関数での誤差について
-
ExcelでPC(パソコン)によって...
-
C言語でセルオートマトンを作成...
-
時刻の比較
-
パソコンで階乗を計算
-
”/”を使わずに割り算したいんで...
-
floatの有効桁数
-
c languageで 簡単な質問があ...
-
2進数の0.2?
-
浮動小数点演算を固定小数点演...
-
VBAのINT関数について
-
ラズベリーパイ>MM-TXS03で温度...
-
EXCELの関数"STDEV(標準偏差)"...
-
Double型について
-
浮動小数演算は実行環境の変化...
-
VBAでの割り算の余りの求め方
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
O(n log n)について2
-
ExcelでPC(パソコン)によって...
-
ExcelのINT関数の計算結果がお...
-
16進数 加算 減算 C言語
-
VB.net Double と...
-
floatの有効桁数
-
三菱シーケンサ(Aシリーズ)で...
-
c languageで 簡単な質問があ...
-
除算を使わずに10で割りたい。
-
VBAでミリ秒まで出力する方法
-
VBAでの割り算の余りの求め方
-
VB6.0での小数点の扱いについて
-
VB6のFIX関数での誤差について
-
有効数字について 以前質問をし...
-
100桁の計算ができなくて困って...
-
浮動小数演算は実行環境の変化...
-
EXCELの関数"STDEV(標準偏差)"...
-
BCD・HEX・BINについて
-
コンピューターは指数関数をど...
-
乱数 なぜ剰余を使うのか
おすすめ情報