29.md

29. Divide Two Integers

Leetcode link

解题思路

本题要求我们在不用乘法、除法与取模运算符的情况下实现一个 32 位整数除法，所得的商向 0 舍入

本题的难点有两个：

• 边界值的判定
• 如何用加法模拟除法

边界值判定比较好处理，下面聊一下如何用加法模拟除法

我们直接用一个例子来说明：62 除以 8

• 要高效且快速逼近被除数，我们考虑 “将除数翻倍” 的方法
• 首先 62/8 可以看成 (62 - 8 * 2 * 2)/8 + 4
• (62 - 32)/8 + 4 可以进一步拆分成 (62 - 32 - 8 * 2)/8 + 4 + 2
• 最后可以变成(62 - 32 - 16 - 8)/8 + 4 + 2 + 1 = 7（向 0 舍入）

C++

class Solution {
public:
  int divide(int dividend, int divisor) {
    // 边界值
    if (dividend == 0)
      return 0;
    if (divisor == 1)
      return dividend;
    if (divisor == -1) {
      if (dividend > INT_MIN)
        return -dividend;
      return INT_MAX;
    }

		// 由于本解法适用两个数都为正，所以这里先保存符号
    int sign = 1;
    if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
      sign = -1;
    }
    // 取个绝对值
    long a = abs(dividend);
    long b = abs(divisor);
    // 核心，本质上就是用递归跑了一次上述思路
    long res = helper(a, b);

    // 最后再把之前保存的符号加回来，顺便处理边界值
    if (sign > 0)
      return res > INT_MAX ? INT_MAX : res;
    return -res;
  }
    
  int helper(long a, long b) {
    if (a < b)
      return 0;
    int count = 1;
    long tempB = b;
    while ((tempB + tempB) <= a) {
      count <<= 1;
      tempB <<= 1;
    }
    return count + helper(a - tempB, b);
  }
};