029. Divide Two Integers[M]

问题

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

思路

这道题难在不能使用乘除取余操作,所以我们只能手动的实现除法,我们来看看如何实现。

我们假设被除数为D,除数为d

手动实现除法

首先,本能想到10 = 2*5 ,10/2 = 5,说明10中有5个2,这里可以用循环来做,看D中间有多少个d就行了。

本能写出一个循环应该不难。

 for(i = 0;dividend - divisor >= 0 ;i+=1)
        {
            dividend = dividend - divisor;
        }

符号

现在有另一个问题,正负数怎么办?我们知道,除法里,异号为负,同号为正,既然不能使用乘除判断,那我们就只能写个判断,这个flag到时候就充当标志。

 boolean flag = (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0);

当然还有更好的实现方式,既然不能用乘除,可以用位运算呀,这和异或操作的含义刚好一样。

 boolean sign = ((dividend < 0) ^ (divisor < 0));

然后,把Dd同时取绝对值就好了。

     long did = Math.abs((long)dividend);
     long dis = Math.abs((long)divisor);

注意:这里除数一定要用long,因为如果最小值取绝对值会溢出

溢出

我们知道,除法可能产生溢出的情况就是D为0,或者D最小值d为-1

if (!divisor || (dividend == Integer.MIN_VALUE && divisor == -1))
            return Integer.MAX_VALUE;

更快的方案

好了,我们可以测试下代码。发现超时,想想也是,上面的循环太慢了。其实我们稍微想一下就可以提速,我们可以采用逐渐逼近的思路:

  • 我们先看i = N个d可不可以
  • 如果可以,我们看看i = 2N个d可以不可以
    • 如果还可以就继续看i = 4N个d可以不可以
      • 直到不可以减,我们让D减去i个d

这里为什么使用2的倍数,因为可以用位运算呀~~

d << 1 就相当与d*2
d << 2 就相当与d*4

我们再用一个i来就记数 i = 0 开始

1 << 0 就相当于1
1 << 1 就相当于2
1 << 2 就相当与4

这里我们用一个临时变量mul_dd的左移操作,注意:mul_d必须为long,因为左移操作很可能溢出!!

现在我们可以写出以下代码了。

public class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1))
            return Integer.MAX_VALUE;
        int i,total = 0;
        //判断正负号
        boolean sign = ((dividend < 0) ^ (divisor < 0));
        //这里必须要long,因为如果最小值取绝对值会溢出
        long did = Math.abs((long)dividend);
        long dis = Math.abs((long)divisor);
        while(did >= dis)
        {
            long mul_dis = dis;
            i = 0;
            //每次左移乘2,记录下来,直到不能减
            while(did >= (mul_dis<<1)) 
            {
                i++;
                mul_dis <<= 1;
            }
            did -= mul_dis;
            total += 1<<i;
        }
        //根据符号返回
        return sign?-total:total;
    }
}

results matching ""

    No results matching ""