LeetCode 29 Divide Two Integers
分析
题目要求不能使用乘法，除法以及取模，而且限制了整型的范围：[-2^31, 2^31-1]。
考虑到除数和被除数的符号可能不一致，为了方便后续处理，我们先统一符号，并使用一个布尔值记录结果的正负形。
一般我们都会考虑将其都转化为正数，但在这里，变成正数会有溢出的问题，原因就在于在题目要求的整型范围内正数的数量比负数的数量少一。
之后，如何在只使用加减法的情况下求出商呢？ 我们可以考虑每次对被除数减去一定数量的除数，循环进行，直到不能再减去， 然后把我们减去的除数的总的数量加起来即结果（当然还要考虑我们之前确定的正负问题）。
暴力方法是每次减去一个，易于理解实现但是会超时。
我们可以考虑每次减去 i 个，如果可以减去的话下次减去 2*i 个，如果不行的话，我们就把被除数减去当前已减去的部分作为新的被除数，递归下去。
基础情况显然是被除数小于除数，此时返回 0 即可。
代码
class Solution {
public:
int divide(int dividend, int divisor) {
bool negative = (dividend > 0) ^ (divisor > 0); // ^ 在 C++ 中为异或运算
if(dividend == INT_MIN && divisor == -1) return INT_MAX; // The only case the result will overfolw
if(dividend > 0) dividend = -dividend; // Turn it into negative beacuse negative part is larger
if(divisor > 0) divisor = -divisor; // Same as above
int mul = divideHelper(dividend, divisor);
return negative ? mul : -mul;
}
private:
int divideHelper(int dividend, int divisor) {
if(dividend > divisor) return 0; // why '>' ? Because they are negative.
int mul = -1;
int sum = divisor;
while(sum >= dividend - sum) { // 就是 2*sum >= dividend，考虑到 2*sum 会溢出，因此就把其转换一下
mul += mul;
sum += sum;
if(sum > 0) break; // Consider the overflow, sum is smaller than dividend if it turns positive
}
return mul + divideHelper(dividend-sum, divisor);
}
};