29. Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Subscribe to see which companies asked this questionc
思路：
首先，最基本的方法是将被除数减去除数，直至被除数小于除数，相减的次数就是商的大小。但是这种方法超时。
在上述方案的基础上，做出适当改进。将除数不断进行左移操作，即乘以2，直至除数大于或者等于被除数。记录左移的次数，即除数放大的倍数，记为temp。然后将被除数与放大之后的除数做减法运算，其效果相当于减去了temp个原来的除数。将temp累加到计数器上。重复这个循环，直至被除数小于除数。最终计数器的值就是商。
注意一点，对于溢出题目给出了超出上限，直接返回上限值。这里需要注意abs(INT_MIN)=INT_MAX+1 .
class Solution { public: int divide(int dividend, int divisor) { if(dividend==0) return 0; long long m= abs((long long) dividend); long long n =abs((long long) divisor); long long ret=0; //是否商是负数 bool flag =(dividend >0) ^(divisor>0); while (m>=n){ long long temp=1; long long a= n; while ((a<<1)<m){ a=a<<1; temp=temp<<1; } ret+=temp; m-=a; } if(!flag){ if(ret>=INT_MAX) return INT_MAX; return ret; } if(ret >INT_MAX) return INT_MIN; return -ret; } };