leetcode[29]Divide Two Integers
3909 ワード
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
If it is overflow, return MAX_INT.
class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend==0||divisor==0)return 0;
int flag=1;
if ((dividend<0&&divisor>0)||(dividend>0&&divisor<0))
flag=0;
if(dividend==divisor)return 1;
long long a=dividend;
long long b=divisor;
a=abs(a);
b=abs(b);
if(a<b)return 0;
long long b0=b;
int res=0;
int icount=0;
int f=1;
while (f)
{
while (a>=b)
{
b<<=1;
icount++;
}
icount--;
b>>=1;
a-=b;
res+=(1<<icount);
if(a<b0)f=0;
else
{
while(a<b)
{
b>>=1;
icount--;
}
}
}
return flag?res:-res;
}
};