【Leetcode】Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

 1 class Solution {
 2 public:
 3     int divide(int dividend, int divisor) {
 4         long long a = dividend < 0 ? -(long long)dividend : dividend;
 5         long long b = divisor < 0 ? -(long long)divisor : divisor;
 6         bool sign = (dividend >= 0 && divisor >= 0) || 
 7                     (dividend <= 0 && divisor <= 0);
 8         long long ans = 0;
 9         while (a >= b) {
10             long long c = b;
11             for (int i = 0; c <= a; c = c << 1, ++i) {
12                 a -= c;
13                 ans += (1 << i);
14             }
15         }
16         return sign ? ans : -ans;
17     }
18 };

View Code

不能用乘、除和取模，那么还可以用加、减和移位。

符号单独考虑。主要从减法出发，可以通过移位加倍被除数从而实现加速。有一点要特别注意的是可能发生溢出，需要用long long类型来进行中间的运算。