在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_diviend和abs_disper的值时，它们会显示负值。

Integer max可以取一个9位数。那么我该如何通过这个测试用例呢？根据这个测试用例，被除数是一个10位数，对于整数范围无效。

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

我该如何解决这个错误？

提前谢谢。

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

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

Answer 3

运行调试器，发现abs_dividend为-2147483648。

则while (abs_dividend >= abs_divisor) {中的比较为假，并且count从不递增。

原来Math.abs(int a):的Javadoc中有解释

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

据推测，这是因为Integer.MAX_VALUE是2147483647，因此无法用int表示正2147483648。(注：2147483648将是Integer.MAX_VALUE + 1 == Integer.MIN_VALUE)