0

私のコードは以下のとおりで、ほとんどの入力で機能しますが、非常に大きな数（特定の例では2147483647を2で割った値）の場合、セグメンテーション違反が発生し、プログラムが機能しなくなります。badd（）関数とbsub（）関数は、それぞれ整数を加算または減算するだけであることに注意してください。

unsigned int bdiv(unsigned int dividend, unsigned int divisor){  
    int quotient = 1; 
    if (divisor == dividend)
    {
        return 1; 
    }
    else if (dividend < divisor)
    {   return -1; }// this represents dividing by zero

    quotient = badd(quotient, bdiv(bsub(dividend, divisor), divisor));

    return quotient;
}

また、bmult（）関数にも少し問題があります。一部の値では機能しますが、-8192x3などの値ではプログラムが失敗します。この関数もリストされています。助けてくれてありがとう。ほんとうにありがとう！

int bmult(int x,int y){
    int total=0;
    /*for (i = 31; i >= 0; i--)
    {
        total = total << 1;
        if(y&1 ==1)
        total = badd(total,x);
    }
    return total;*/ 
    while (x != 0)
    {
        if ((x&1) != 0)
        {
            total = badd(total, y);
        }
        y <<= 1;
        x >>= 1;
    }
    return total; 
}
4

2 に答える 2

1

bdiv の問題は、再帰の深さが原因である可能性が最も高いです。あなたが与えた例では、約1073741824フレームをスタックに入れ、基本的に割り当てられたメモリを使い果たします。

実際、この関数が再帰的である必要がある本当の理由はありません。スタックの問題を軽減する反復ソリューションに簡単に変換できます。

于 2012-10-04T04:25:29.563 に答える
1

乗算では、この行はオーバーフローして切り捨てられるyため、badd()間違った入力が得られます。

y<<=1;

この行：

x>>=1;

ネガティブxウェルにはうまくいきません。ほとんどのコンパイラは、ここでいわゆる算術シフトを行います。これは、0 が最上位ビットにシフトされる通常のシフトのようなものですが、ひねりを加えれば、最上位ビットは変更されません。したがって、負の値を右にシフトすると、最終的に -1 になります。また、右にシフトされた -1 は -1 のままであり、乗算で無限ループが発生します。

符号なし整数の乗算アルゴリズムを使用して、符号付き整数を乗算しないでください。コアで符号付き型を使用している場合、うまく機能する可能性はほとんどありません (あったとしても)。

符号付き整数を乗算する場合は、まず符号なし型を使用して、符号なし整数の乗算を実装できます。そして、実際に符号付き乗算に使用できます。これは、符号付き整数の 2 の補数表現を使用するため、事実上すべてのシステムで機能します。

例 (16 ビットの 2 の補数整数を想定):

-1 * +1 -> 0xFFFF * 1 = 0xFFFF -> 符号付きに戻す -> -1
-1 * -1 -> 0xFFFF * 0xFFFF = 0xFFFE0001 -> 16 ビットに切り詰めて符号付きに変換 -> 1

部門では、次の2行

else if (dividend < divisor)
{   return -1; }// this represents dividing by zero

明らかに間違っています。考えてみてください、1/2 はいくらですか? -1 や (unsigned int)-1 ではなく、0 です。

また、UINT_MAX/1 はいくらですか。ですUINT_MAX。したがって、除算関数が返されるUINT_MAXか(unsigned int)-1、2 つの値が同じであるため、違いがわからない場合があります。呼び出し元にオーバーフローを通知するには、別のメカニズムを使用する必要があります。

ああ、もちろん、この行：

quotient = badd(quotient, bdiv(bsub(dividend, divisor), divisor));

商が大きいと予想される場合、スタック オーバーフローが発生します。これを再帰的に行わないでください。少なくとも、代わりにループを使用してください。

于 2012-10-04T04:34:12.870 に答える