029-Divide Two Integers-不用乘除取模来实现整型除法

96 阅读 0 评论 64 点赞

我是靠谱客的博主受伤吐司，这篇文章主要介绍029-Divide Two Integers-不用乘除取模来实现整型除法，现在分享给大家，希望可以做个参考。

不用乘除取模来实现整型除法。

这题的关键在于用左移操作<<来取代乘法，每左移一位则相当于数字翻倍。保证每一轮的被除数大于除数的前提下，不断翻倍除数直到最大，倍数记录于结果，然后做差并将其记为下一轮的被除数。这里需要注意的是int类型的边界：

复制代码

1
2
最小值：Integer.MIN_VALUE=-2147483648
最大值：Integer.MAX_VALUE=2147483647

比如-2147483648/-1，答案是2147483648，但是越界了，int内就会变成-2147483648。所以采取的一个操作就是将除数与被除数一起转化为长整型long，来避免越界问题。

对于一些特殊的运算情况，独立出来写if语句有助于提升程序效率，比如除数被除数相等，除数为0，除数为正负1之类的。

下面贴代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class divide2 {
public static int divide(int dividend, int divisor) {
if( divisor==1 ) return dividend;
if( ( dividend == Integer.MIN_VALUE && divisor == -1 ) || divisor==0) return Integer.MAX_VALUE;
int sign = (dividend<0) ^ (divisor<0)? -1:1, result = 0;
if( Math.abs(dividend) == Math.abs(divisor) ) return sign;
long dvd = Math.abs((long)dividend), dvs = Math.abs((long)divisor);
long sub;
int subR;
while( dvd > dvs ) {
sub = dvs;
subR = 1;
while( dvd >= ( sub<<1 ) ) {
sub = sub << 1;
subR = subR << 1;
}
dvd = dvd - sub;
result = result + subR;
}
return sign * result;
    }
public static void main(String []args) {
System.out.println(divide(-2147483648,2));
}
}