思路
题目要求将两数相除,不使用乘法、除法和 mod 运算符,那最朴素的做法就是每次减被除数、计数器++但是这样做很明显会超时。改进思路是对被除数减的时候使用倍增的方法(二分)。
- 在Java中,当t=Integer.MIN_VALUE时(t取相反数依旧是它本身)此时可能存在越界问题,因此都用负数进行计算.
代码
class Solution {
public int divide(int dividend, int divisor) {
if(divisor==0||(dividend==Integer.MIN_VALUE&&divisor==-1)) return Integer.MAX_VALUE;
boolean flag = (dividend>0&&divisor>0)||(dividend<0&&divisor<0);
int res = 0;
dividend=-Math.abs(dividend);
divisor= -Math.abs(divisor);
while(dividend<=divisor){
int tmp = divisor;
int c=1;
while(dividend-tmp<=tmp){
tmp<<=1;
c<<=1;
}
dividend-=tmp;
res+=c;
}
return flag?res:-res;
}
}