剑指 Offer II 001. 整数除法

• 剑指 Offer II 001. 整数除法
• • 题目
  • 题解

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

注意：

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示:

-2³¹ <= a, b <= 2³¹ - 1
b != 0

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/xoh6Oh
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路
比如求解64/3,意思在问64中有多少个3
减法的思路就是:就是在64里，1个3，2个3 … n个3，这样找
位运算 1个3，2个3，4个3，8个3，以2的n次方这样找

不能用乘除法，或者要求优化 乘除法的性能问题，都可以优先考虑 位运算。

先快速逼近结果
以11/3为例

1. 11>3 结果至少为1
2. 让3翻倍为6 11>6=3*2 结果至少为2
3. 让6翻倍为12 11>12=3*2² 说明结果应该在2~4之间
4. 也就是说2再加上某个数，这个数是多少呢？我让11减去刚才最后一次的结果6，剩下5,5是3的几倍
5. 递归

先记录商的符号，然后将被除数和除数都转为负数进行计算

为什么转为负数？
负数的最大值 的理论绝对值，是比正数的最大值 大1的。如果转成正数，负数可能会溢出

递归三部曲
递归的参数和返回值
递归的参数是被除数dividend和除数divisor，返回值是商

function div(int dividend, int dividend )

递归的结束条件
当dividend>divisor时商为0，递归结束。需要注意除数和被除数都是负数

function div(int dividend, int dividend ){
	 if(dividend > divisor) return 0;
}

本层递归的逻辑
先快速逼近结果

let sum = divisor; // divisor商的范围，翻倍的次数
let count = 1; //记录商
while (dividend <= sum+sum) {
     // 每次翻倍
      count = count + count;
      sum = sum + sum
}//count为范围的最小值
return count + div(dividend -sum,divisor);

代码

var divide = function(a, b) {
    const MAX = 2147483647, MIN = -2147483648;
 
    if(a==0)return 0;//情况1:0/b=0
    if(b==1)return a;//情况2:a/1=a
    if(b==-1){
       return a==MIN? MAX:-a; //如果是最小值，则转换为最大值，否则直接取反
    }
    let flag = 1; 
    if((a>0&&b<0) || (a<0&&b>0)){//记录符号
        flag = -1;
    }
    //除数和被除数都转为负数
    a= a>0? -a:a;
    b= b>0? -b:b;   
    let res =  div(a,b);
   
    return flag ==1? res:-res;
}
   function div(dividend, divisor){
      
	 if(dividend > divisor) return 0;//注意是负数
     let sum = divisor; // divisor商的范围，翻倍的次数
     let count = 1; //记录商
     while (dividend <= (sum+sum)) {//注意是负数
        // 每次翻倍
        count = count + count;
        sum = sum + sum;//如果改为位运算，到-2147483648后<<1会变成0
     }//count为范围的最小值
    return count + div(dividend -sum,divisor);
    }