java計算兩數(shù)相除的商

這篇文章給大家分享java計算兩數(shù)相除的商的方法，相信大部分人都還沒學(xué)會這個技能，為了讓大家學(xué)會，給大家總結(jié)了以下內(nèi)容。

1 題目

LeetCode第29題,計算兩數(shù)相除的商，不允許使用乘法，除法，求模運算符。

2 減法

首先判斷結(jié)果是否需要加上負號，將商置為0后，被除數(shù)不斷減去除數(shù)，同時商自增。最后根據(jù)是否有負號返回相應(yīng)的商。

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這兩個數(shù)，是4字節(jié)的int的最小值與最大值，在java中，它們可用Integer.MIN_VALUE與Integer.MAX_VALUE表示，當一個int為Integer.MIN_VALUE時，取反也是這個數(shù)：


最簡單最粗暴的解決方案就是使用long，long可以放下-Integer.MIN_VALUE，因此，直接將被除數(shù)與除數(shù)的類型改成long，返回值轉(zhuǎn)為long即可。
但是提交了一下，超時：

所以對除數(shù)1與-1進行特判一下：

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

若除數(shù)是1直接返回被除數(shù)，這時不需要考慮溢出，若是除數(shù)是-1，需要特判一下被除數(shù)是否為int的最小值，因為-Intger.MIN_VALUE也是Intger.MIN_VALUE，題目也說了返回int的最大值。
然后信心十足地提交了：

慘淡。

3.2 負數(shù)

溢出的原因，就算因為負數(shù)的存儲范圍比正數(shù)多1，就算因為那兩個可惡的-2147483648與2147483647.
上面的做法是判斷結(jié)果的負號，然后將被除數(shù)與除數(shù)都轉(zhuǎn)為正數(shù)來計算，可以換一種思路，將被除數(shù)與除數(shù)都轉(zhuǎn)為負數(shù)來計算：

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;
}

結(jié)果從0開始自增，while循環(huán)的條件改成被除數(shù)小于等于除數(shù)而不是之前的被除數(shù)大于等于除數(shù)，然后對得出的商判斷正負與邊界，如果是負數(shù)，判斷商的相反數(shù)是否是int的最小值，若是的話，表示真正的商為2147483648，負溢出，返回int的最小值，若不是負數(shù)，判斷商是否為int的最小值，若是的話，表示真正的商為2147483648，正溢出，返回int的最大值。

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

3.3 翻倍與移位

速度慢的原因，是因為減法。因此需要改進減法，使被除數(shù)更快地逼近除數(shù)。
對于被除數(shù)為2147483647，除數(shù)為1的情況，需要減2147483647次，才能得出結(jié)果，所以，使用翻倍，第一次減1，第二次減2，第三次減4，以此類推。
但是怎么翻倍怎么操作呢?

a *= 2 ?

題目說不能用乘法運算符。
作為一個現(xiàn)代的程序員，總不能這樣翻倍吧？

a += a;

這時就輪到位移運算符登場了，左移一位，相當于乘2，右移一位相當與除2：

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

總體思路是設(shè)置一個tempResult與一個tempDivisor，不斷將tempResult與tempDivisor翻倍，直到被除數(shù)大于等于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的最小值，會溢出，跳出循環(huán)后會導(dǎo)致被除數(shù)減去一個正數(shù)而不是一個負數(shù)，這樣相當于增大了被除數(shù)導(dǎo)致計算的結(jié)果錯誤。

4 遞歸

遞歸可以減少設(shè)置一個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;
}

代碼與迭代基本相同，結(jié)束條件為被除數(shù)大于除數(shù)，在進入遞歸前需要對被除數(shù)與除數(shù)處理正負：

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;
}

以上就是java計算兩數(shù)相除的商的詳細內(nèi)容，代碼示例簡單明了，如果在日常工作遇到此問題。通過這篇文章，希望你能有所收獲，更多詳情敬請關(guān)注億速云行業(yè)資訊頻道！