Divide two integers without using multiplication, division and mod operator.
-----------------------------------------------------------------
keep multiplying divisor by 2 until divisor is larger than dividend, then divide it by 2
compute the difference between divisor and dividend, set it as the new dividend
class Solution {
public:
int divide(int dividend, int divisor) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
long long a = abs((double)dividend);;
long long b = abs((double)divisor);
int sign = 1;
if (dividend < 0) sign *= -1;
if (divisor < 0) sign *= -1;
int total = 0;
while (a >= b) {
long long c = b;
int count = 1;
while (a >= (c<<1)) {
c = c << 1;
count = count << 1;
}
a = a - c;
total += count;
}
return total*sign;
}
};
Java, updated on Aug-6th-2018
原来同上，就是不断的对以下数组里的数进行循环相减，然后更新被除数
[divisor * 2, divisor * 2 ^ 2, divisor * 2 ^ 3, divisor * 2 ^ 4 ...]
注意处理溢出
class Solution {
public int divide(int dividendInt, int divisorInt) {
long dividend = Math.abs((long)dividendInt);
long divisor = Math.abs((long)divisorInt);
int sign = 1;
if (dividendInt < 0) sign *= -1;
if (divisorInt < 0) sign *= -1;
long count = 0;
while (dividend >= divisor) {
int tempCount = 1;
long tempDivisor = divisor;
while ((tempDivisor << 1) < dividend) {
tempCount <<= 1;
tempDivisor <<= 1;
}
dividend -= tempDivisor;
count += tempCount;
}
if (count > Integer.MAX_VALUE) {
if (sign == 1) return Integer.MAX_VALUE;
return Integer.MIN_VALUE;
}
return (int) count * sign;
}
}
