题目:
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT. (Medium)
分析:
题目要求不使用乘除和模运算实现两个整数除法。
第一个思路就是每次把count加等被除数自身判定,只到count<=除数,并且count + 被除数 > 除数时即为结果。
但是考虑到可能有 MAX_INT / 1这种情况,肯定华丽超时。
然后考虑使用移位运算,每次将count加等被除数左移一位(*2),满足条件后跳出循环,并且把除数 -= count,再来,只到除数 < 被除数挑出外循环。
注意:
这种数学题不是很好写(从AC率只有15%左右可以看出)。除了想清楚算法本身,
还要注意正负数处理,注意int范围处理(一般改成long long最后再判定比较简便,比如reverse integer)
代码:
class Solution {
public:
int divide(int dividend, int divisor) {
long long ldividend = dividend;
long long ldivisor = divisor;
int flag = ;
if (ldividend < ) {
ldividend = -ldividend;
flag = -flag;
}
if (ldivisor < ) {
ldivisor = -ldivisor;
flag = -flag;
}
long long result = ;
while (ldivisor <= ldividend) {
long long count = ldivisor;
long long temp = ;
long long tempDividend = ldividend;
while ( !(count <= tempDividend && (count << ) > tempDividend)) {
count <<= ;
temp <<= ;
}
result += temp;
ldividend -= count;
}
if (flag < ) {
if (result > 0x80000000) {
return 0x7FFFFFFF;
}
else {
return -result;
}
}
else {
if (result > 0x7FFFFFFF) {
return 0x7FFFFFFF;
}
else {
return result;
}
} }
};