在Java中不使用乘法、除法和取模运算符来进行两个整数的除法

Question

我写了一段代码，用于找出两个数相除后的商，但不使用乘法、除法或取模运算符。

我的代码：

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;

}

我的代码通过了一些测试用例，例如dividend=-1，divisor=1或dividend=1且divisor=-1。但是它无法通过像dividend = --2147483648和divisor =-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。

我该如何解决这个错误？

提前感谢您。

- Encipher

Answer 1

尝试使用以下位运算来完成这个任务：

public static int divideUsingBits(int dividend, int divisor) {
        // handle special cases
        if (divisor == 0)
            return Integer.MAX_VALUE;
        if (divisor == -1 && dividend == Integer.MIN_VALUE)
            return Integer.MAX_VALUE;

        // get positive values
        long pDividend = Math.abs((long) dividend);
        long pDivisor = Math.abs((long) divisor);

        int result = 0;
        while (pDividend >= pDivisor) {
            // calculate number of left shifts
            int numShift = 0;
            while (pDividend >= (pDivisor << numShift)) {
                numShift++;
            }

            // dividend minus the largest shifted divisor
            result += 1 << (numShift - 1);
            pDividend -= (pDivisor << (numShift - 1));
        }

        if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
            return result;
        } else {
            return -result;
        }
    }

- KayV

---

为什么要使用这一行代码 result += 1 << (numShift - 1); 而不是简单的 result+= (numShift-1)？ - amrx

Answer 2

我是这样解决的。在可能出现左移导致溢出的情况下，优先选择数据类型long而不是int。在处理过程中，在最开始处理边界条件以避免输入值被修改。这个算法基于我们在学校使用的除法技巧。

public int divide(int AA, int BB) {
    // Edge case first.    
    if (BB == -1 && AA == Integer.MIN_VALUE){
        return Integer.MAX_VALUE;   // Very Special case, since 2^31 is not inside range while -2^31 is within range.
    }
    long B = BB;
    long A = AA;

    int sign = -1;
    if ((A<0 && B<0) || (A>0 && B>0)){
        sign = 1;
    }
    if (A < 0) A = A * -1;
    if (B < 0) B = B * -1;

    int ans = 0;
    long currPos = 1; // necessary to be long. Long is better for left shifting.
    while (A >= B){
        B <<= 1; currPos <<= 1;
    }
    B >>= 1; currPos >>= 1;
    while (currPos != 0){
        if (A >= B){
            A -= B;
            ans |= currPos;
        }
        B >>= 1; currPos >>= 1;
    }
    return ans*sign;
}

- Saurav Sahu

---

OP要求不使用乘法运算符。 - Yash Kumar Verma

Answer 3

使用调试器运行后发现abs_dividend为-2147483648。

然后在while (abs_dividend >= abs_divisor) {的比较中为false，count从未递增。

结果在Math.abs(int a)的Javadoc中有解释：

请注意，如果参数等于Integer.MIN_VALUE，即最小可表示int值，则结果是相同的负值。

大概是因为Integer.MAX_VALUE为2147483647，所以无法用int表示正数2147483648。(注意：2147483648将是Integer.MAX_VALUE + 1 == Integer.MIN_VALUE)

- mlinkus