Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Solution 1: Use long
public class Solution {
public int divide(int dividend, int divisor) {
return divide((long) dividend, (long) divisor);
}
private int divide(long a, long b) {
boolean pos=true;
if (a<0) pos=!pos;
if (b<0) pos=!pos;
a=Math.abs(a);
b=Math.abs(b);
int i=0;
while (a>=b<<i) i++;
i--;
long res=0; //res need to be long
while (i>=0) {
if (a>=b<<i) {
a-=b<<i;
res|=(long)1<<i; //pay attention here, otherwise 2147483648 will be negtive
}
i--;
}
if (!pos) res=-res;
if (res>Integer.MAX_VALUE || res<Integer.MIN_VALUE) return Integer.MAX_VALUE;
return (int)res;
}
}
Solution 1: Do not use long but deal corner case first.
public class Solution {
public int divide(int dividend, int divisor) {
boolean pos=true;
boolean min=false;
if (divisor==0) return Integer.MAX_VALUE;
if (divisor==Integer.MIN_VALUE) {
if (dividend==Integer.MIN_VALUE) return 1;
else return 0;
}
if (dividend==Integer.MIN_VALUE) {
if (divisor==1) return Integer.MIN_VALUE;
else if (divisor==-1) return Integer.MAX_VALUE;
else {
min=true;
dividend+=Math.abs(divisor);
}
}
if (dividend<0) {
dividend=-dividend;
pos=!pos;
}
if (divisor<0) {
divisor=-divisor;
pos=!pos;
}
int i=0;
while (dividend>>i>=divisor) i++;
i--;
int res=0;
for (; i>=0; i--) {
if (dividend>=divisor<<i) {
dividend-=divisor<<i;
res|=1<<i;
}
}
if (min) res++;
if (!pos) res=-res;
return res;
}
}
没有评论:
发表评论