参考资料
练习题 icon lost
交流讨论
笔记
img lost

题目描述

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2

来源:力扣(LeetCode)题目链接
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

注意:

  • 被除数和除数均为 32 位有符号整数
  • 除数不为 0
  • 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [ − 2 31 −2^{31} 231, 2 31 − 1 2^{31} − 1 2311]。本题中,如果除法结果溢出,则返回 2 31 − 1 2^{31} − 1 2311

题解一(基于快速乘法思想)

class Solution {
public:
    int divide(int dividend, int divisor) {
    	if(! dividend) return 0;
        //diviend有可能 = INT_MIN 如果此时除数为1或-1 若int 溢出 = -1
        long long res = 0;
        //diviend有可能 = INT_MIN 转成int 溢出 = -1
        long long dividend_abs = abs((long long)dividend);
        long long divisor_abs = abs((long long)divisor);
        if (dividend_abs < divisor_abs) return 0;
        long long t = divisor_abs, p = 1;
        while (dividend_abs > (t << 1)) {
            t <<= 1;
            p <<= 1;
        }
        res += p + divide(dividend_abs - t, divisor_abs); //递归
        //判断符号
        if ((dividend ^ divisor) < 0) res = -res;
        //题目特别说明
        return res > INT_MAX ? INT_MAX : res;
    }
};

执行结果

题解二(二分思想+快速乘法)

试图不用long,但是失败了
有时间再改

class Solution {
public:
    int divide(int dividend, int divisor) {
        //处理比较特殊的情况
        if(! dividend) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1) return dividend > INT_MIN ? -dividend : INT_MAX;
        //记录符号
        bool isT = true;
        if((dividend ^ divisor) < 0) isT = false;
        //转化为负数,防溢出 
        if(dividend > 0) dividend = -dividend;
        if(divisor > 0) divisor = -divisor;
        
        //二分处理
        int left = 0;
        int right = dividend; 
        long mid = 0;
        while(left > right){
            mid = abs(left+right-1) >> 1;
            auto con = quickMulti(mid, divisor); 
            if(con == dividend){
                return  isT ? mid : -mid;                   
            }else if(con < dividend)
                right = -mid+1;
            else left = -mid-1;
        }
        mid = abs(left+right-1) >> 1;
        return  isT ? mid : -mid+1;
    
        
    }
    int quickMulti(int a, int b){
        int res = 0;
        int _b = abs(b);
        while(_b){
            if(_b & 1 == 1) res += a;
            _b >>= 1;
            a <<= 1; 
        }

        return b < 0 ? -res : res;
    }
};
资料来源 Leetcode 29 两数相除
博客作者 qq_43402798
前往答题
我的笔记