Divide two integers without using multiplication, division and mod operator.
If it is overflow, return 2147483647
Given dividend = 100 and divisor = 9, return 11.
LeetCode上的原题，请参见我之前的博客Divide Two Integers。
解法一：
class Solution { public: /** * @param dividend the dividend * @param divisor the divisor * @return the result */ int divide(int dividend, int divisor) { if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX; long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0; int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; if (n == 1) return sign == 1 ? m : -m; while (m >= n) { long long t = n, p = 1; while (m >= (t << 1)) { t <<= 1; p <<= 1; } res += p; m -= t; } return sign == 1 ? res : -res; } };
解法二：
class Solution { public: /** * @param dividend the dividend * @param divisor the divisor * @return the result */ int divide(int dividend, int divisor) { long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0; if (m < n) return 0; while (m >= n) { long long t = n, p = 1; while (m > (t << 1)) { t <<= 1; p <<= 1; } res += p; m -= t; } if ((dividend < 0) ^ (divisor < 0)) res = -res; return res > INT_MAX ? INT_MAX : res; } };
解法三：
class Solution { public: /** * @param dividend the dividend * @param divisor the divisor * @return the result */ int divide(int dividend, int divisor) { long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0; if (m < n) return 0; long long t = n, p = 1; while (m > (t << 1)) { t <<= 1; p <<= 1; } res += p + divide(m - t, n); if ((dividend < 0) ^ (divisor < 0)) res = -res; return res > INT_MAX ? INT_MAX : res; } };
本文转自博客园Grandyang的博客，原文链接：两数相除[LintCode] Divide Two Integers ，如需转载请自行联系原博主。
