题目描述

整数除法
给定两个整数 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

解题思路①

用减法实现的除法
比如7/3，
用7 - 3 = 4 > 0，够减，那么结果就是 1 + 4/3
4 - 3 = 1 > 0，够减，结果就是 1 + 1 + 1/3
1 - 3 = -2 < 0，不够减，所以最后结果就是1+1=2
在加上int的32位边界数值处理逻辑。
想法容易实现，完全可行，但是没想到这居然会超时😢

实现代码

  1.     public int divide(int a,int b){
  2.         int res = 0;
  3. //        sign 为结果符号
  4.         int sign = 1;
  5.         // 除数为0
  6.         if(b==0){
  7.             return Integer.MAX_VALUE;
  8.         }
  9.         // 边界值处理
  10.         if(a == Integer.MIN_VALUE&&b==-1){
  11.             return Integer.MAX_VALUE;
  12.         }
  13.         if(a == Integer.MIN_VALUE){
  14.             if(b>0){
  15.                 a = a + b;
  16.             }else{
  17.                 a = a-b;
  18.             }
  19.             res = res +1;
  20.         }
  21.         if(a==0){
  22.             return res;
  23.         }
  24.         if(a<0){
  25.             a = -a;
  26.             sign = -sign;
  27.         }
  28.         if(b<0){
  29.             b = -b;
  30.             sign = -sign;
  31.         }
  32.         // 余数
  33.         a = a -b;
  34.         //当除数大于0时，继续减少
  35.         while (a>=0){
  36.             res = res + 1;
  37.             a = a -b;
  38.         }
  39.         return sign == 1 ? res : -res;
  40.     }

解题思路②/③：leetcode题解

思路①自己想到的，奈何超时，当时想到了位运算，看题解也是，尝试自己解决，无果，不知道该怎么运用位运算，遂看题解。

②减法优化

22/3 = 7
22 - 3 = 19 > 0 k = 1(k 为除数的倍数)
19 - (3 + 3) = 13 > 0 k = 2
12 - (6 + 6) = 1 > 0 k = 4
1 - (12 +12) < 0 k = 8 失败，减小k
1 - (6 + 6) < 0 k = 4 失败，减小k
1 - (3 + 3) < 0 k = 2 失败，减小k
1 - 3 < 0 k = 1 失败，k无法减小，得结果
res = 1 + 2 + 4 = 7

③ 位运算优化

22 - 3 2^31 < 0 (3<<31)
22 - 3 2^30 < 0 (3<<30)
22 - 3 2^29 < 0 (3<<29)
……
22 - 3 2^3 = -2 < 0 (3<<3)
22 - 3 2^2 = 10 > 0 (3<<2) k = 2^2 = 4
(10 - 32^2一定<0，所以下一步直接从2^1次幂开始减)
10 - 3 2^1 = 4 > 0 (3<<1) k = 2^1 = 2
4 - 3 2^0 = 1 > 0 (3<<0) k = 2^0 = 1
此时移位运算到0位，一定不会再够除
res = 4 + 2 + 1 = 7

  1.     /*
  2.      * 作者：tangweiqun
  3.      * 思路：位运算实现的除法，与优化的除法方法是类似的，每次减少一倍除数->尝试每次减少多倍的除数
  4.      *      从一倍开始尝试 -> 从可能的最高倍数开始尝试
  5.      * 链接：https://leetcode-cn.com/problems/xoh6Oh/solution/jian-dan-yi-dong-javac-pythonjs-zheng-sh-e8r6/
  6.      * 来源：力扣（LeetCode）
  7.      * */
  8.     // 时间复杂度：O(1)
  9.     public int bitDivide(int a, int b) {
  10.         if (a == Integer.MIN_VALUE && b == -1)
  11.             return Integer.MAX_VALUE;
  12.         int sign = (a > 0) ^ (b > 0) ? -1 : 1;
  13.         a = Math.abs(a);
  14.         b = Math.abs(b);
  15.         int res = 0;
  16.         for (int i = 31; i >= 0; i--) {
  17.             // 首先，右移的话，再怎么着也不会越界
  18.             // 其次，无符号右移的目的是：将 -2147483648 看成 2147483648
  19.             // 注意，这里不能是 (a >>> i) >= b 而应该是 (a >>> i) - b >= 0
  20.             // 这个也是为了避免 b = -2147483648，如果 b = -2147483648
  21.             // 那么 (a >>> i) >= b 永远为 true，但是 (a >>> i) - b >= 0 为 false
  22.             if ((a >>> i) - b >= 0) { // a >= (b << i)
  23.                 a -= (b << i);
  24.                 res += (1 << i);
  25.             }
  26.         }
  27.         return sign == 1 ? res : -res;
  28.     }

时间及空间复杂度分析

Tips

  • 优化乘法/除法，可以考虑位运算