29. Divide Two Integers
题目描述：
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
题目翻译
在不使用乘\除\mod运算的情况下计算两个整数的除法
如果计算过程中遇到溢出，返回MAX_INT值
解题方案
标签： Math
思路：
首先理清题意，即输入两个整数计算除法，如15/3；但不许用乘法除法和模运算，自然我们会想到用被除数一步一步减去除数，将所做减法的总数加起来即得结果，这样做如果遇到被除数远大于除数绝对会超时，所以我们需要用到位操作。
依然用15/3的例子，所以15是被除数 ，3是除数，用减法的思想：
第一次减去3得到12
第二次减去3得到9 //注意位运算中相当于将3=0011左移一位变为6=0110
第三次减去3得到6
第四次减去3得到3 //注意位运算中相当于将6=0110左移一位变为12=1100
按照位运算对12再次左移得到24，此时24>15，所以无法左移，即最多可以减去12
通过上面的过程可知把3向左移动两次（减了4次）获得12，而为了保存这个次数，只要同时将1左移两次。
现在过程到了15 = 3 * 4 + 3 ，剩下的余数3让它循环上面的过程，减去一次3得到0，因为不需要左移，所以计算 1 << 0 来保存次数
最后将所有保存的次数加起来即得结果
针对题目的第二句话需要注意会溢出的情况：
- 除数为0
- -max转为正数时会溢出，比如 -max/-1 = max + 1 溢出
代码：
class Solution {
public:
int divide(int dividend, int divisor) {
if (!divisor || (dividend == INT_MIN && divisor == -1))
return INT_MAX;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
long long dvd = labs(dividend);
long long dvs = labs(divisor);
int res = 0;
while (dvd >= dvs) {
long long temp = dvs, multiple = 1;
while (dvd >= (temp << 1)) {
temp <<= 1;
multiple <<= 1;
}
dvd -= temp;
res += multiple;
}
return sign == 1 ? res : -res;
}
};