otal Accepted: 54356 Total Submissions: 357733 Difficulty: Medium
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
1.除法转换为加法，加法转换为乘法，y个x相加的结果就是x*y.
假设结果为dividend的一半，用此值与divisor相乘，如果相乘结果大于dividend则，high=dividend,然后继续二分
/**
两个整数相除也可能会溢出，最小负数除以-1就溢出了
*/
class Solution {
public:
long long int multiply(long long x,long long int y)
{
if(y==){
return x;
}
long long int res = multiply(x,y>>);
res = (&y) ? (res<<) + x: (res<<);
return res;
} int divide(int dividend, int divisor) {
long long int l_dividend = fabs(dividend);
long long int l_divisor = fabs(divisor); if(l_dividend < l_divisor){
return ;
}
if((dividend==INT_MIN && divisor==-) || divisor==){
return INT_MAX;
} int sign = ((dividend>>)^(divisor>>)) ? -:; long long int low = ,high =l_dividend; while(low<=high){
long long int mid = low+((high-low)>>);
long long int res = multiply(l_divisor,mid);
if(res == l_dividend){
return mid*sign;
}else if(res<l_dividend){
low = mid+;
}else{
high = mid-;
}
} return (low-)*sign;
}
};
2.除法分配率：a/b = (x+y)/b = x/b+y/b ，其中a=x+y;
42/6;
dividend = 42，divisor=6;
42 = 6*2*2 + 18 ---> 42/6 = 24/6 + 18/6
18 = 6*2 + 6; ----> 18/6 = 12/6 + 6
6 = 6+0; ----> 6/6 = 6/6 + 0
所以：42/6 = 2*2+2+1=7；
/**
两个整数相除也可能会溢出，最小负数除以-1就溢出了
*/
class Solution {
public:
int divide(int dividend, int divisor) {
long long int l_dividend = fabs(dividend);
long long int l_divisor = fabs(divisor); if(l_dividend < l_divisor){
return ;
}
if((dividend==INT_MIN && divisor==-) || divisor==){
return INT_MAX;
} int sign = ((dividend>>)^(divisor>>)) ? -:;
int res = ;
while(l_dividend >= l_divisor){
long long int tmp = l_divisor;
int occur_times = ;
while(tmp <= l_dividend){
tmp = tmp<<;
occur_times++;
}
res += (<<(occur_times-));
l_dividend -= (tmp>>);
} return res*sign;
}
};