Given two integers dividend
and divisor
, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend
by divisor
.
The integer division should truncate toward zero.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Note:
- Both dividend and divisor will be 32-bit signed integers.
- The divisor will never be 0.
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
题目要求不使用乘除和取余的运算得到除法的结果,我们第一个想到的肯定是减法,除法的本质就是减法嘛,但是减法的时间复杂度很不友好,如果被除数是Integer.MAX_VALUE,除数是1,那就很麻烦了
在这个基础上我们想到了更高级一点的操作方法,位移运算,<<1表示把字节左移一位相当于*2,我们不断扩大除数divisor,直到它再扩大于被除数,这个时候我们需要缩小被除数,就用这个被除数减去当前的除数然后再重复之前的过程,就得到了我们想要的结果。这里需要注意的是测试样例存在integer.MAX_VALUE和-1的特殊情况,所以我们要使用long来帮助存储判断
class Solution {
public int divide(int dividend, int divisor) {
long m=Math.abs((long)dividend);
long n=Math.abs((long)divisor);
long res=0,tag=Integer.MAX_VALUE;
if(m<n) return 0;
while(m>=n){
long temp=n,count=1;
while(m>(temp<<1)){
temp<<=1;
count<<=1;
}
m-=temp;
res+=count;
}
if((dividend<0)^(divisor<0)) res=-res;
return (int)(res>tag ? tag:res);
}
}