Description
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Discussion
不用乘除和模运算来算整数除法。
最简单而直观的方法就是用被除数一直减除数，直到为0。
另外，我们可以采用左移右移来提高效率。我们知道任何一个整数都可以表示成下面的二进制形式：
num = a0 * 20 + a1 * 21 + a2 * 22 + …… + an * 2n
我们可以把商值表示为上述形式。开始时让除数左移到恰好小于被除数的一个除数，并记下左移位数digit。每次用被除数减去除数，可以就给商answer加上2digit，然后除数右移1位，digit减1。循环执行。
算法的时间复杂度为O(logn)。
C++ Code
class Solution {
public:
int divide(int dividend, int divisor) {
//除数为0，直接退出
if(divisor == 0)
{
return INT_MAX;
}
bool symbol = ((dividend ^ divisor) >> 31) == 0; //商符号
int answer = 0; //商
//对除数和被除数为最小数的情况进行特殊处理
if(dividend == INT_MIN)
{
if(divisor == -1)
{
return INT_MAX;
}
dividend += abs(divisor);
answer ++;
}
if(divisor == INT_MIN)
{
return answer;
}
dividend = abs(dividend);
divisor = abs(divisor);
int digit = 0; //商二进制位数
while(divisor <= (dividend >> 1))
{
divisor <<= 1;
digit ++;
}
while(digit >= 0)
{
if(dividend >= divisor)
{
answer += (1 << digit);
dividend -= divisor;
}
divisor >>= 1;
digit --;
}
return symbol ? answer : -answer;
}
};