使用位运算模拟除法。
思路很简单。首先可以想到拿被除数减去除数,直到不能减为止。
但是这是很low的,我们可以用倍增的思想,任何数字都可以由2^x+2^y+2^z......组成的。
所以我们用被除数减去 除数*2^x ,那么商就+= 2^x ,然后减去得到差,继续再减 除数的2^x
class Solution {
public:
int divide(int dividend, int divisor) {
if(dividend==0)
return 0;
int sign=1;
if(dividend < 0 && divisor>0)
{
sign=0;
}
if(dividend > 0 && divisor<0)
{
sign=0;
}
long long int ans=0;
long long int divid = abs((long long int)dividend);
long long int divis = abs((long long int)divisor);
for(int i=31;i>=0;i--)
{
if( (divis << i ) <= divid)
{
ans += (1 << i);
divid -= (divis << i);
}
}
ans = abs(ans);
if(sign==0)
ans = ~ans +1;
if(ans > 2147483647)
ans = 2147483647;
if(ans < -2147483648 )
ans = -2147483648;
return ans;
}
};
LeetCode 29. Divide Two Integers
原文:https://www.cnblogs.com/dacc123/p/11191406.html