java計算兩數相除的商

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

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

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