LintCode_两个整数相除

本文主要是介绍LintCode_两个整数相除，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

将两个整数相除，要求不使用乘法、除法和 mod 运算符。如果溢出，返回 2147483647 。

样例：给定被除数 = 100 ，除数 = 9，返回 11。

算法思想：

方法一：（这是开始自己想出来的，算法思想简单，缺点是，循环次数多，运行速度慢）

如果不能采用乘除运算方法，那么可以采用加减方式，当然还要（1）、注意分类：正正，正负，负正，负负；（2）、溢出问题；

    public static int divide(int dividend, int divisor) {if(divisor==0){return 2147483647;}if(dividend==0){return 0;}if(dividend==-2147483648&&divisor==-2147483648){return 1;}int result=0;//如果被除数为负数，除数为正数if(dividend<0&&divisor>0){//循环将除数加至被除数中，直至被除数大于或者等于0while((dividend+divisor)<=0){       dividend+=divisor;result--;}}else if(dividend>0&&divisor>0){//被除数与除数都是正数，直接计算，result++while((dividend-divisor)>=0){dividend-=divisor;result++;}}else if(dividend>0&&divisor<0){//被除数为正数，除数为负数，将除数转变成正数，result--while((dividend+divisor)>=0){dividend+=divisor;result--;}}else if(dividend<0&&divisor<0){while((dividend-divisor)<=0&&result<2147483647){//可能(-2147483648)/(-1)=2147483648,刚好导致溢出dividend=dividend-divisor;result++;}}return result;}

注： 此题在测试过程中，最纠结的就是碰到-2147483648等的溢出问题，例如被除数和除数都是-2147483648时，如果，在最开始没有使用

<pre name="code" class="java" style="color: rgb(113, 113, 113);">        if(dividend==-2147483648&&divisor==-2147483648){return 1;}

语句，result最终结果为 2147483647。在负负情况下添加添加打印result和dividend的语句，可以看到result和dividend在while循环中的结果，很奇怪；如果被除数和除数是其他数据，运行结果正常。因此， 这不是逻辑问题，而是溢出！

方法二：百度了下别人的做法，发现可以使用位运算，减少循环步骤，大大减少了运算时间，在被除数很大，除数很小的时候很有优势。因为左移一位相当于数字乘2；所以有时左移右移运算配合加减法，就相当于乘除法；

    public static  int divide(int dividend, int divisor) {  // Write your code here  //判断dividend与divisor是否是同符号，同符号，结果为正，不同符号，结果为负数Boolean resultGreatThanZero = true;  if(dividend>0&&divisor<0||dividend<0&&divisor>0)  resultGreatThanZero = false;  //保存最终结果int ret = 0;//将d1与d2都转变成正数运算long d1 = abs((long)dividend);  long d2 = abs((long)divisor);  while(d1>=d2)  {  long temp = d2;  long cnt = 1;  while(d1>=temp)  {  d1-=temp;  ret+=cnt;//左移一位，相当于cnt乘2；//不能直接使用乘法运算，那么可以采用左移代表乘法，可以减少运算步骤cnt = cnt<<1;  temp = temp<<1;  }  }  if(!resultGreatThanZero)  ret*=-1;  //考虑到溢出if(ret<(long)INT_MIN||ret>(long)INT_MAX)  return (int) INT_MAX;  return (int) ret;  }  private static long abs(long divisor) {if(divisor<0){divisor=divisor*(-1);}return divisor;
}

这篇关于LintCode_两个整数相除的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---