189 8069 5689

java计算两数相除的商-创新互联

这篇文章给大家分享java计算两数相除的商的方法,相信大部分人都还没学会这个技能,为了让大家学会,给大家总结了以下内容。

创新互联专注于企业营销型网站、网站重做改版、托里网站定制设计、自适应品牌网站建设、成都h5网站建设商城网站建设、集团公司官网建设、外贸营销网站建设、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为托里等各大城市提供网站开发制作服务。

1 题目

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

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 溢出

java计算两数相除的商
-2147483648与2147483647这两个数,是4字节的int的最小值与大值,在java中,它们可用Integer.MIN_VALUE与Integer.MAX_VALUE表示,当一个int为Integer.MIN_VALUE时,取反也是这个数:
java计算两数相除的商
java计算两数相除的商
最简单最粗暴的解决方案就是使用long,long可以放下-Integer.MIN_VALUE,因此,直接将被除数与除数的类型改成long,返回值转为long即可。
但是提交了一下,超时:
java计算两数相除的商
所以对除数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的大值。
然后信心十足地提交了:
java计算两数相除的商
惨淡。

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的大值。
java计算两数相除的商
快了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的最小值,会溢出,跳出循环后会导致被除数减去一个正数而不是一个负数,这样相当于增大了被除数导致计算的结果错误。
java计算两数相除的商

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计算两数相除的商

以上就是java计算两数相除的商的详细内容,代码示例简单明了,如果在日常工作遇到此问题。通过这篇文章,希望你能有所收获,更多详情敬请关注创新互联行业资讯频道!

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


文章题目:java计算两数相除的商-创新互联
路径分享:http://jkwzsj.com/article/ccddjg.html

其他资讯