描述

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

  • 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

示例

示例 1：

  1. 输入：a = 15, b = 2
  2. 输出：7
  3. 解释：15/2 = truncate(7.5) = 7

示例 2：

  1. 输入：a = 7, b = -3
  2. 输出：-2
  3. 解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

  1. 输入：a = 0, b = 1
  2. 输出：0

示例 4：

  1. 输入：a = 1, b = 1
  2. 输出：1

提示

  • -231 <= a, b <= 231 - 1
  • b != 0

解题思路

  • 首先，讨论边界情况，只有当被除数为 Integer.MIN_VALUE , 除数为 -1 时，结果会溢出，所以先对这种情况特殊处理。
  • 对于符号的处理，我们可以将被除数或者除数取相反数，使得它们符号相同。如果我们将被除数和除数都变为正数，那么可能会导致溢出。例如当被除数为 −231 时，它的相反数 231 产生了溢出。因此，我们可以考虑将被除数和除数都变为负数，这样就不会有溢出的问题，在编码时只需要考虑 1 种情况了。
  • 因为题目限制，不能使用乘法和除法，因此，我们需要使用 快速乘 算法，通过加法实现乘法。

代码

  1. class Solution {
  2.     public int divide(int a, int b) {
  3.         if (a == 0x80000000 && b == -1) { // 0x80000000 就是 Integer.MIN_VALUE
  4.             return 0x7FFFFFFF; // 0x7FFFFFFF 就是 Integer.MAX_VALUE
  5.         }
  6.         int n = 2; // 确定最后结果的符号，n 为 1 时结果取相反数
  7.         if (a > 0) {
  8.             a = -a;
  9.             n--;
  10.         }
  11.         if (b > 0) {
  12.             b = -b;
  13.             n--;
  14.         }
  15.         int result = 0;
  16.         while (a <= b) {  // 快速乘模板
  17.             int value = b;
  18.             int q = 1; //统计商
  19.             while (value >= 0xc0000000 && value + value >= a) { // value >= 0xc0000000 是为了保证value + value 不会溢出
  20.                 value += value;
  21.                 q += q;
  22.             }
  23.             result += q;
  24.             a -= value;
  25.         }
  26.         return n == 1 ? -result : result;
  27.     }
  28. }