# 29. Divide Two Integers

Given two integers `dividend` and `divisor`, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, `8.345` would be truncated to `8`, and `-2.7335` would be truncated to `-2`.

Return _the quotient after dividing _`dividend` by`divisor`.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: `[−2^31, 2^31 − 1]`. For this problem, if the quotient is strictly greater than `2^31 - 1`, then return `2^31 - 1`, and if the quotient is strictly less than `-2^31`, then return `-2^31`.

Example 1:

``````**Input:** dividend = 10, divisor = 3
**Output:** 3
**Explanation:** 10/3 = 3.33333.. which is truncated to 3.
``````

Example 2:

``````**Input:** dividend = 7, divisor = -3
**Output:** -2
**Explanation:** 7/-3 = -2.33333.. which is truncated to -2.
``````

Constraints:

• `-2^31 <= dividend, divisor <= 2^31 - 1`
• `divisor != 0`

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

``````class Solution {
public:
int divide(int dividend, int divisor) {
long m = labs(dividend), n = labs(divisor), res = 0;
if (m < n) return 0;
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;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/29

https://leetcode.com/problems/divide-two-integers/

https://leetcode.com/problems/divide-two-integers/discuss/13524/summary-of-3-c-solutions

https://leetcode.com/problems/divide-two-integers/discuss/13407/C%2B%2B-bit-manipulations

https://leetcode.com/problems/divide-two-integers/discuss/142849/C%2B%2BJavaPython-Should-Not-Use-%22long%22-Int

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation