迭代。eg: 65 / 8 = (65 – 8) / 8 + 1 = (57 – 16) / 8 + 2 + 1 = (41 – 32) / 8 + 4 + 2 + 1 = 9 / 8 + 7 = (9 – 8) / 8 + 1 + 7 = 1 / 8 + 8 = 8
因为有 INT_MAX 和 INT_MIN 的干扰,还得排除一下特殊情况
c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Solution { public: int divide(int dividend, int divisor) { if (divisor == INT_MIN) { if (dividend == INT_MIN)return 1; else return 0; } int flag = 1, fix = 0; if (dividend == INT_MIN) { if (divisor == 1)return INT_MIN; else if (divisor == -1)return INT_MAX; dividend = INT_MAX; divisor = -divisor; fix = 1; } if (dividend > 0 && divisor < 0) { divisor = -divisor; flag = -1; } else if (dividend < 0 && divisor > 0) { dividend = -dividend; flag = -1; } else if (dividend < 0 && divisor < 0) { dividend = -dividend; divisor = -divisor; } if (divisor > dividend)return 0; int result = 1 + iteration(dividend - divisor + fix, 1, divisor, divisor); return result * flag; } int iteration(int divide, int result, int now, int base) { if (divide < base) return 0; else if (now > divide) return iteration(divide, 1, base, base); else if (now <= divide) return result + iteration(divide - now, result << 1, now << 1, base); return 0; } }; |