每天AC系列(十三):两数相除

2024-03-16 14:24:58

1 题目

LeetCode第29题,计算两数相除的商，不允许使用乘法，除法，求模运算符。

2 减法

首先判断结果是否需要加上负号，将商置为0后，被除数不断减去除数，同时商自增。最后根据是否有负号返回相应的商。

boolean negative = true;
if((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))
    negative = false;
dividend = dividend > 0 ? dividend : -dividend;
divisor = divisor > 0 ? divisor : -divisor;
int result = 0;
while(dividend >= divisor)
{
    dividend -= divisor;
    ++result;
}
return negative ? -result : result;

3 思考

3.1 溢出

-2147483648与2147483647这两个数，是4字节的int的最小值与最大值，在java中，它们可用Integer.MIN_VALUE与Integer.MAX_VALUE表示，当一个int为Integer.MIN_VALUE时，取反也是这个数：

最简单最粗暴的解决方案就是使用long，long可以放下-Integer.MIN_VALUE，因此，直接将被除数与除数的类型改成long，返回值转为long即可。
但是提交了一下，超时：

所以对除数1与-1进行特判一下：

if(divisor == 1)
    return dividend;
if(divisor == -1)
{
    if(dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE;
    return -dividend;
}

若除数是1直接返回被除数，这时不需要考虑溢出，若是除数是-1，需要特判一下被除数是否为int的最小值，因为-Intger.MIN_VALUE也是Intger.MIN_VALUE，题目也说了返回int的最大值。
然后信心十足地提交了：

惨淡。

3.2 负数

溢出的原因，就算因为负数的存储范围比正数多1，就算因为那两个可恶的-2147483648与2147483647.
上面的做法是判断结果的负号，然后将被除数与除数都转为正数来计算，可以换一种思路，将被除数与除数都转为负数来计算：

dividend = dividend > 0 ? -dividend : dividend;
divisor = divisor > 0 ? -divisor : divisor;
int result = 0;
while(dividend <= divisor)
{
    dividend -= divisor;
    ++result;
}
if(negative)
{
    if(-result == Integer.MIN_VALUE)
        return Integer.MIN_VALUE;
    return -result;
}
else
{
    if(result == Integer.MIN_VALUE)
        return Integer.MAX_VALUE;
    return result;
}

结果从0开始自增，while循环的条件改成被除数小于等于除数而不是之前的被除数大于等于除数，然后对得出的商判断正负与边界，如果是负数，判断商的相反数是否是int的最小值，若是的话，表示真正的商为2147483648，负溢出，返回int的最小值，若不是负数，判断商是否为int的最小值，若是的话，表示真正的商为2147483648，正溢出，返回int的最大值。

快了600ms，还是有效果的。

3.3 翻倍与移位

速度慢的原因，是因为减法。因此需要改进减法，使被除数更快地逼近除数。
对于被除数为2147483647，除数为1的情况，需要减2147483647次，才能得出结果，所以，使用翻倍，第一次减1，第二次减2，第三次减4，以此类推。
但是怎么翻倍怎么操作呢?

a *= 2 ?

题目说不能用乘法运算符。
作为一个现代的程序员，总不能这样翻倍吧？

a += a;

这时就轮到位移运算符登场了，左移一位，相当于乘2，右移一位相当与除2：

a <<= 1; // a *= 2
a >>= 1; // a /= 2

总体思路是设置一个tempResult与一个tempDivisor，不断将tempResult与tempDivisor翻倍，直到被除数大于等于tempDivisor或tempDivisor溢出，然后把tempResult增加到result上面。

while(dividend <= divisor)
{
    int tempDivisor = divisor;
    int tempResult = 1;
    while(dividend < (tempDivisor<<1) && tempDivisor > (Integer.MIN_VALUE >> 1))
    {
        tempDivisor <<= 1;
        tempResult <<= 1;
    }
    dividend -= tempDivisor;
    result += tempResult;
}

其中：

tempDivisor > (Integer.MIN_VALUE >> 1)

这个while中的判断很重要，如果tempDivisor大于int的最小值的一半，则tempDivisor左移1位后会小于Integer.MIN_VALUE，也就是小于int的最小值，会溢出，跳出循环后会导致被除数减去一个正数而不是一个负数，这样相当于增大了被除数导致计算的结果错误。

4 递归

递归可以减少设置一个result变量，直接在返回值里加上即可：

public int div(int dividend,int divisor)
{
    if(dividend <= divisor)
    {
        int tempDivisor = divisor;
        int tempResult = 1;
        while(dividend < (tempDivisor<<1) && tempDivisor > (Integer.MIN_VALUE >> 1))
        {
            tempDivisor <<= 1;
            tempResult <<= 1;
        }
        return tempResult + div(dividend-tempDivisor,divisor);
    }
    return 0;
}

代码与迭代基本相同，结束条件为被除数大于除数，在进入递归前需要对被除数与除数处理正负：

public int divide(int dividend,int divisor)
{
    boolean negative = (dividend > 0) ^ (divisor > 0);
    int result = div(dividend > 0 ? -dividend : dividend,divisor > 0 ? -divisor : divisor);
    if(negative) return -result;
    return result == Integer.MIN_VALUE ? Integer.MAX_VALUE : result;
}

5 源码

github

码云

码农公寓