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; } }
No comments:
Post a Comment