剰余演算を論理演算と加減算に置き換える方法

質問

剰余(割算の余り)を求める演算を論理演算と加減算とビットシフトのみで行う方法がありましたら教えてください。

言語はC/C++ではなくても大丈夫です(ロジックだけでも)。

回答No.4

noname#30727 · ベストアンサー

私も割り算命令の無いCPU用にアセンブラで作ります。
符号ありは少し複雑なので、符号なしで・・・。

// x/yの余りを求める(8bit/8bitの余りの場合)
unsigned char mod(unsigned char x, unsigned char y)
{
unsigned int a = x;
unsigned int b = y;
b <<= 7;
for (int i = 0; i < 8; i++) {
if (a >= b) {
a -= b;
}
b >>= 1;
}
return (unsigned char)a;
}

お礼

質問の背景まで、察してくださるとは思いませんでした。
ありがとうございます。

回答No.3

tatsu99

既に回答がでていますが、
スピードを無視したアルゴリズムですが、
下記の関数は、わり算を行って、商と余りを返す関数です。
// a / b を求める
// 商はsho、余りはamariに格納される
// a >= 0, b > 0が前提
void sub_dev(int a , int b , int *sho, int *amari){
*sho = 0;
while(a >= b){
(*sho)++;
a -= b;
}
*amari = a;
}
a>=0,b>0が前提です。（そうでない場合は誤動作します）
int a = 10;
int b = 3;
int sho,amari;
sub_deb(a,b,&sho,&amari);のように使います。
ところで、どうして剰余を求める時「論理演算と加減算とビットシフトのみで行う方法」が必要なのかということ自体に非常に興味があります。よろしければ、このような質問をされた理由を教えていただけませんでしょうか。

お礼

ありがとうございます。

No.4の回答にも書かれているのと同じような理由です。
実際はWindows搭載のコンピュータで実装しています。
したがって、%演算子を使えばいいのですが、
除算器と乗算器が無いものとして、実装を行いたいからです。
特に組込みのLSIを利用するものとして、作っています。
価格の都合で、あまり高価な回路にできないのだそうです。

回答No.2

パんだ パンだ（@Josquin）

ｘ÷ｙの商がａ、余りがｂだとすると
ｘ＝ａｙ＋ｂ　⇔　ｂ＝ｘ－ａｙ
という形になるので、ｘからｙをａ回引けば余りになります。
余りだけなら、

ｘがｙより小さければそのｘが余り　…（１）
ｘ＝ｘ－ｙ
（１）に戻る

でいかがでしょう？
商も必要なら、繰り返しの回数を数えればいいと思います。
２進数ではどうなるかわかりませんが。

お礼

ありがとうございます。
引き算のループに落すということですね。

回答No.1

arukamun

こういったロジックは小学校の算数に戻りましょう。

例）
１３６÷３＝

　＿０４５＿
３）１３６
　＿１２＿
　　　１６
　　＿１５＿
　　　　１

これは１０進数での計算ですね。
これを２進数で考えて見てください。
10001000÷00000011＝

　　＿００１０１１０１＿
１１）１０００１０００
　　＿０１１＿
　　　　　１０１
　　　　＿０１１＿
　　　　　　１００
　　　　　＿０１１＿
　　　　　　　　１００
　　　　　　　＿０１１＿
　　　　　　　　　　１

ビットシフトと加減算と比較しかしていませんよね。
がんばれぇ！

お礼

ありがとうございます。
まさに算数の考え方ですね。