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 };

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

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