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() 函数也有点麻烦。它适用于某些值，但程序对于诸如 -8192 乘以 3 之类的值会失败。还列出了此函数。提前感谢您的帮助。对此，我真的非常感激！

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

在乘法中，这条线会溢出和截断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

在划分以下两行

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

是完全错误的。想一想，1/2 是多少？它是 0，而不是 -1 或 (unsigned int)-1。

此外，UINT_MAX/1 是多少？是UINT_MAX。因此，当您的除法函数返回时UINT_MAX，(unsigned int)-1您将无法区分，因为这两个值是相同的。您确实应该使用不同的机制来通知调用者溢出。

哦，当然还有这一行：

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

当商预计很大时，将导致堆栈溢出。不要递归地执行此操作。至少，请改用循环。

于 2012-10-04T04:34:12.870 回答
1

您的 bdiv 问题很可能是由递归深度引起的。在您给出的示例中，您将大约 1073741824 帧放入堆栈，基本上用完了分配的内存。

事实上，这个函数没有真正的理由需要递归。我可以很容易地转换为迭代解决方案，从而缓解堆栈问题。

于 2012-10-04T04:25:29.563 回答