除算を使わずに10で割りたい。

質問

加算、減算、シフト、論理演算、ループ、等を使って
除算を使わずに10で割る方法は無いものでしょうか？
また、近似値を求めてから誤差を修正する方法でも構いません。

ただし、ループで10を引き続けてカウントする方法は除外させてください。

言語はCでお願いします。

回答No.16

mtaka2 · ベストアンサー

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

vipasigaru

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

colder

負数には、対応していない。

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

titokani

基本的には引き算に展開することになると思います。
ただ、そのまま引いたのでは確かに回数が多くなりますので、適当にシフトを使います。
例えば、１２３４５６÷１０を計算する場合、
最上位の値１をまず10で割ります。
1÷10=0余り1
この余りと次の位を合わせた数を１０で割ります。
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

noname#144013

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

rinkun

整数ということですので、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

pyonmae

No.8です。
もはや本筋ではお役に立てそうもなく、スレ汚しになってしまいますが・・・。

>私が「除外させて下さい」と書いた10で引き続けてカウントする方法
>のほうが全然分かりやすくて単純だと思うのですが、
>なにか、問題があって使われないのでしょうか？

鋭いご指摘ですね。私も思わず一瞬、「アレ？何がいいんだっけ？」と思ってしまいました。
違いは、「ループ回数」です。
10引き続けてカウント方法だと、被除数の値/10回のループが発生するのに対して、私が提示した方法では、ビット数回分のループで計算が終了します。
被除数が100や1000くらいのうちは良いですが、1億とかになってくると計算時間に随分と差が出てきます。

・・・とは言え、いまどきのPCでは全く問題にならないのでしょうね・・・。
私も勉強になります。

お礼

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

やはり、ループの回数ですか。
多倍長の除算に拡張したいと思っている身としては
大きな問題になります。

そう思うと、復元法なんかはずいぶん魅力的な方法に見えますね。

疑問にお答えくださって、ありがとうございました。

回答No.9

ts3m-ickw

No.3です。
除数が10固定だけど小数点以下もあり‥‥難しいなぁ。被除数が整数で良くて余りを出していいのならNo.2さんのアルゴリズムを除算に置き換えればいいんだけど。それじゃダメらしいし。

とりあえず除算アルゴリズムにはいろいろあって紹介しきれないので、Googleしておきます。ただ、ループなしってのは私の知る限りでは無いですね。除数を10固定にしてうまく応用できれば、あるいは‥‥？
http://www.google.co.jp/search?hl=ja&suggon=0&q=%E9%99%A4%E7%AE%97%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0&btnG=%E6%A4%9C%E7%B4%A2&lr=

お礼

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

申し訳ありません。
小数点以下は切捨てで大丈夫です。
整数による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

pyonmae

有名ドコロですが筆算方式はどうでしょう。
/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;
}

のほうが全然分かりやすくて単純だと思うのですが、
なにか、問題があって使われないのでしょうか？
ちょっと納得できないでいます。

しかしながら、とても参考になりました。
コードまで貼って頂きありがとうございました。

回答No.7

Tasuke22

ANo.5.6.です。

すみません勘違いです。
ダメですね。

お礼

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

いろいろと試していただいたようで申し訳ありませんでした。

依然、スマートでエレガントな方法受け付けて降ります。

いろいろ、方法があるとこちらとしても、ありがたく思います。
さまざまなご意見をいただけることに感謝しております。

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

回答No.6

Tasuke22

ANo5です。

訂正です。

10のビットを反転し1を足して掛けます。