Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
解题思路:
既然不呢个用乘除和取模运算,只好采用移位运算,可以通过设置一个length代表divisor向左的做大移位数,直到大于dividend,然后对length做一个循环递减,dividend如果大于divisor即进行减法运算,同时result加上对应的值,注意边界条件,JAVA实现如下:
static public int divide(int dividend, int divisor) {
if (divisor == 0)
return Integer.MAX_VALUE;
boolean isNeg = dividend < 0;
if (divisor < 0)
isNeg = !isNeg;
int length = 0;
long longdividend = Math.abs((long) dividend);
long longdivisor = Math.abs((long) divisor), result = 0;
while (longdividend >= longdivisor) {
longdivisor = longdivisor << 1;
length++;
}
while (length >= 0) {
if (longdividend >= longdivisor) {
result += Math.pow(2, length);
longdividend -= longdivisor;
}
longdivisor = longdivisor >> 1;
length--;
}
if (result > Integer.MAX_VALUE && !isNeg)
result = (long) Integer.MAX_VALUE;
return isNeg ? -(int) result : (int) result;
}