两个整数相除

xiaoxiao2021-02-28  46

将两个整数相除,要求不使用乘法、除法和 mod 运算符。

如果溢出,返回 2147483647 。

样例

给定被除数 = 100 ,除数 = 9,返回 11。

1.超时的二分法(里面的求和增加了复杂度):

class Solution { public: /** * @param dividend the dividend * @param divisor the divisor * @return the result */ int divide(int dividend, int divisor) { // Write your code here if(divisor==0)return 2147483647; bool flag=true; if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))flag=false; long long a=llabs((long long)dividend); long long b=llabs((long long)divisor); long long sum=0; long long start=0; long long end=a; long long mid=0; while(a>=b) { sum=0; mid=(start+end)/2; for(int i=0;i<mid;i++) sum+=b; if(sum-a>0)end=mid-1; else if(a-sum>=b)start=mid+1; else break; } if(!flag)mid=-mid; if(mid>INT_MAX||mid<INT_MIN)return 2147483647; return mid; } };

2.利用二进制性质(移位操作)的巧妙方法(遇到很大的被除数像指数一样快)

class Solution { public: /** * @param dividend the dividend * @param divisor the divisor * @return the result */ int divide(int dividend, int divisor) { // Write your code here if(divisor==0)return 2147483647; bool flag=true; if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))flag=false; long long a=llabs((long long)dividend); long long b=llabs((long long)divisor); long long ans=0; while(a>=b) { long long cnt=1; long long temp=b; while(a>=temp) { a-=temp; ans=ans+cnt; cnt=cnt<<1; temp=temp<<1; } } if(!flag)ans=-ans; if(ans>INT_MAX||ans<INT_MIN)return 2147483647; return ans; } };

转载请注明原文地址: https://www.6miu.com/read-1100250.html

最新回复(0)