29. 两数相除

迈不过友情╰ 2022-09-09 04:56 112阅读 0赞

[https://leetcode-cn.com/problems/divide-two-integers/][https_leetcode-cn.com_problems_divide-two-integers]

难度中等638

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

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

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

**示例 1:**

输入: dividend = 10, divisor = 3
    输出: 3
    解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

**示例 2:**

输入: dividend = 7, divisor = -3
    输出: -2
    解释: 7/-3 = truncate(-2.33333..) = -2

**提示：**

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

通过次数105,445提交次数508,618

class Solution {
        public int divide(int dividend, int divisor) {
            long INT_MAX = 2147483647;
            long INT_MIN = (-INT_MAX - 1);
            if(divisor == 1) return dividend;
            if(divisor == -1){
                if(dividend > INT_MIN) return -dividend;
                return (int)INT_MAX;
            }
            int ans  = 0;
            int x = 0;
            int flag = 0;
            long d1 = dividend;
            long d2 = divisor;
            if(d1<0 || d2<0) flag = 1;
            if(d1<0 && d2<0) flag = 0;
    
            if(d1<0) d1 =-d1;
            if(d2<0) d2 = -d2;
           
            // while(d1>0 && d2>0)
            // {
            //         d1 -= d2;
            //         if(d1>=0)ans++;
            // }
            long d3 = d2;
        while(d1>=d3)
        { 
            d2 = d3;
            ans = 0;
            while(d1>=d2)
            {
                d2 +=d2;
                ans +=ans;
                if(ans == 0) ans =1;
            }
            d2 = d2>>1;
            // System.out.println(d1-d2);
            d1 -=d2;
            x += ans;
        }
          
            if(flag==1) x = -x;
            return x;
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_divide-two-integers]: https://leetcode-cn.com/problems/divide-two-integers/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a6e02efbf84148a9a74b140a7c3555bb.png