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

问题描述

我写下了一个代码，该代码在将两个数相除之后却不使用乘法，除法或mod运算符来找出商.

I write down a code which find out quotient after dividing two number but without using multiplication,division or mod operator.

我的代码

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语句.

My code passes the test cases like dividend=-1, divisor=1 or dividend=1 and divisor=-1. But it cannot pass the test case like dividend = --2147483648 and divisor =-1. However I have a if statement when both inputs are negative.

  if(fun_dividend<0 && fun_divisor<0){
        return count;
    }

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

When my inputs are -2147483648 and -1 it returned zero. I debugged my code and find out that it cannot reach the the inner statements of while loop. It just check the while loop and terminated and execute

 if(fun_dividend<0 && fun_divisor<0){
        return count;
    }

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

It is very obvious, both inputs are negative, so I was using Math.abs function to make them positive. But when I try to see the values of variables abs_dividend and abs_divisor they show me negative values.

最大整数可以为9位数字.那么我怎么能通过这个测试用例呢?根据此测试用例，除数是10位数字，在整数范围内无效.

Integer max can take a 9 digit number. So how could I pass this test case? As per this test case dividend is a 10 digit number which is not valid for a integer range.

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

As per the test case the output that I get should be 2147483647.

我该如何解决该错误?

先谢谢您.

推荐答案

我是通过这种方式解决的.优先向数据类型long而不是int左移时有溢出的可能.从一开始就处理边缘情况，以避免在过程中修改输入值.该算法基于我们以前在学校中使用的除法技术.

I solve it this way. Give preference to data type long over int wherever there is a chance of overflow upon left-shift. Handle the edge case at the very beginning to avoid the input values getting modified in the process. This algorithm is based upon the division technique we used to make use in school.

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;
}

这篇关于在Java中不使用乘法，除法和mod运算符将两个整数相除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！