# 29. Divide Two Integers 两数相除

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Difficulty: Medium

t
(除数)
p
(计数)
res
(结果)
m
(被除数)
t
(除数)
p
(计数)
res
(结果)
m
(被除数)
t
(除数)
p
(计数)
res
(结果)
m
(被除数)
2 1 32 36 2 1 48 4 2 1 50 0
4 2 4 2 4 2
8 4 8 4
16 8 16 8
32 16 32 16
64 32

### 解法1

``````class Solution {
public:
int divide(int dividend, int divisor) {
if (divisor==0||(dividend==INT_MIN&&divisor==-1)) return INT_MAX;
int sign = ((dividend<0)^(divisor<0))?-1:1;
long long m = abs((long long)dividend),n = abs((long long)divisor), res = 0;
if (n==1) return sign==1?m:-m;
while (m>=n)
{
long long t = n,p = 1;
while(m>=(t<<1))
{
t <<= 1;
p <<= 1;
}
res += p;
m -= t;
}
return sign==1?res:-res;
}
};
``````

### 解法2

``````class Solution {
public:
int divide(int dividend, int divisor) {
long long m = abs((long long)dividend),n = abs((long long)divisor), res = 0;
if (m<n) return 0;
while(m>=n)
{
long long t = n,p=1;
while(m>(t<<1)){
t<<=1;
p<<=1;
}
res += p;
m -= t;
}
if ((dividend<0)^(divisor<0)) res = -res;
return res>INT_MAX?INT_MAX:res;
}
};
``````

### 解法3

``````class Solution {
public:
int divide(int dividend, int divisor) {
long long m = abs((long long)dividend),n = abs((long long)divisor),res = 0;
if (m<n) return 0;
long long t = n,p=1;
while(m>=(t<<1))
{
t<<=1;
p<<=1;
}
res += p+divide(m-t,n);
if ((dividend<0)^(divisor<0)) res = -res;
return res>INT_MAX?INT_MAX:res;
}
};
``````