28
03/2015
[LeetCode] Divide Two Integers
Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
解题思路：
考虑到可能会溢出，因此可用long long类型强制转化int类型。另外，这种类型题目一般都是先确定符号位，将所有的值转化成正数，然后再进行相关操作。（与之前的分数转循环小数类似）
另外，注意32位的int类型的最大值和最小值形式。我的算法有点不美，就是可能在位数不同的机器上结果不对。若有更好办法，欢迎留言。
class Solution {
public:
int divide(int dividend, int divisor) {
int MIN_INT = 1 << (sizeof(int)*8 - 1);
int MAX_INT = 0x7fffffff;
if (divisor == 0){
return MAX_INT;
}
long long result = 0;
//先确定符号
bool positive = (dividend ^ divisor) >= 0 ? true : false;
long long dividendL = (long long)dividend;
long long divisorL = (long long)divisor;
//取绝对值
if (dividendL < 0){
dividendL = -dividendL;
}
if (divisorL < 0){
divisorL = -divisorL;
}
//为0的情况，不做判断也可以work
if (dividendL < divisorL){
return 0;
}
while (dividendL >= divisorL)
{
long long base = 1;
long long tempDivisorL = divisorL;
while (dividendL >= (tempDivisorL << 1)){ //考虑到右移运算会让被除数失真，因此用除数左移
tempDivisorL <<= 1;
base <<= 1;
}
result += base;
dividendL -= tempDivisorL;
}
if (!positive){
result = -result;
}
//判断是否溢出
if (result>MAX_INT || result<MIN_INT){
return MAX_INT;
}
return (int)result;
}
};转载请注明：康瑞部落 » [LeetCode] Divide Two Integers
0 条评论