在Java中不使用乘法，除法和mod运算符将两个整数相除

Question

我写下了一个代码，该代码在将两个数相除后不使用商，除法或mod运算符就能找出商。

我的密码

public int divide(int dividend, int divisor) {

    int diff=0,count=0;

    int fun_dividend=dividend;

    int fun_divisor=divisor;

    int abs_dividend=abs(dividend);

    int abs_divisor=abs(divisor);

    while(abs_dividend>=abs_divisor){

        diff=abs_dividend-abs_divisor;

        abs_dividend=diff;

        count++;

    }

    if(fun_dividend<0 && fun_divisor<0){

        return count;

    }

    else if(fun_divisor<0||fun_dividend<0) {

        return (-count);

    }

    return count;

}

我的代码通过了像红利= -1，除数= 1或红利= 1和除数= -1这样的测试用例。但它无法通过测试用例，例如股息= --2147483648和除数= -1。但是，当两个输入均为负时，我有一个if语句。

  if(fun_dividend<0 && fun_divisor<0){

        return count;

    }

当我的输入是-2147483648和-1时，它返回零。我调试了代码，发现它无法到达while循环的内部语句。它只是检查while循环并终止并执行

 if(fun_dividend<0 && fun_divisor<0){

        return count;

    }

很明显，两个输入均为负，因此我使用Math.abs函数将它们设为正。但是，当我尝试查看变量abs_dividend和abs_divisor的值时，它们显示的是负值。

整数最大值可以为9位数字。那么我怎么能通过这个测试用例呢？根据该测试案例，红利是10位数字，对于整数范围无效。

根据测试用例，我得到的输出应该是2147483647。

我该如何解决该错误？

Answer 1

我这样解决。优先考虑数据类型long在int只要有在左移溢出的机会。从一开始就处理边缘情况，以避免在过程中修改输入值。该算法基于我们过去在学校中使用的除法技术。public int divide(int AA, int BB) {&nbsp; &nbsp; // Edge case first.&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; if (BB == -1 && AA == Integer.MIN_VALUE){&nbsp; &nbsp; &nbsp; &nbsp; return Integer.MAX_VALUE;&nbsp; &nbsp;// Very Special case, since 2^31 is not inside range while -2^31 is within range.&nbsp; &nbsp; }&nbsp; &nbsp; long B = BB;&nbsp; &nbsp; long A = AA;&nbsp; &nbsp; int sign = -1;&nbsp; &nbsp; if ((A<0 && B<0) || (A>0 && B>0)){&nbsp; &nbsp; &nbsp; &nbsp; sign = 1;&nbsp; &nbsp; }&nbsp; &nbsp; if (A < 0) A = A * -1;&nbsp; &nbsp; if (B < 0) B = B * -1;&nbsp; &nbsp; int ans = 0;&nbsp; &nbsp; long currPos = 1; // necessary to be long. Long is better for left shifting.&nbsp; &nbsp; while (A >= B){&nbsp; &nbsp; &nbsp; &nbsp; B <<= 1; currPos <<= 1;&nbsp; &nbsp; }&nbsp; &nbsp; B >>= 1; currPos >>= 1;&nbsp; &nbsp; while (currPos != 0){&nbsp; &nbsp; &nbsp; &nbsp; if (A >= B){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; A -= B;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans |= currPos;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; B >>= 1; currPos >>= 1;&nbsp; &nbsp; }&nbsp; &nbsp; return ans*sign;}

Answer 2

与调试器一起运行，发现它abs_dividend为-2147483648。那么in的比较结果while (abs_dividend >= abs_divisor) {为假，count并且永远不会递增。原来的解释是在Javadoc中Math.abs(int a)：请注意，如果参数等于Integer.MIN_VALUE的值（最负的可表示int值），则结果是相同的值，该值为负。大概是因为Integer.MAX_VALUE2147483647，所以无法用来表示正2147483648&nbsp;int。（注意：2147483648将是Integer.MAX_VALUE + 1 == Integer.MIN_VALUE）