*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

**Note**: This is my first version of a solution for this problem. Some have questioned whether or not the bitwise shifts used in this version should count as multiplication/division, so I've also posted an alternate solution taking advantage of the algebraic qualities of logarithms.

####
Leetcode Problem #29 (*Medium*): Divide Two Integers

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Given two integers

`dividend`

and`divisor`

, divide two integers without using multiplication, division, and mod operator.Return the quotient after dividing

`dividend`

by`divisor`

.The integer division should truncate toward zero, which means losing its fractional part. For example,

`truncate(8.345) = 8`

and`truncate(-2.7335) = -2`

.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, assume that your function returns`2^31 − 1`

when the division result overflows.

####
*Examples:*

*Examples:*

Example 1: Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2: Input: dividend = 7, divisor = -3 Output: -2 Explanation: 7/-3 = truncate(-2.33333..) = -2.

Example 3: Input: dividend = 0, divisor = 1 Output: 0

Example 4: Input: dividend = 1, divisor = 1 Output: 1

####
*Constraints:*

*Constraints:*

`-2^31 <= dividend, divisor <= 2^31 - 1`

`divisor != 0`

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

The naive approach here would be to use a loop to just work down the difference between the dividend (**A**) and the divisor (**B**) through subtraction, but that's obviously not a very efficient solution.

Instead, we can use **bit manipulation** to simulate multiplication/division. Since a **bitwise shift** to the left is the equivalent of a multiplication by **2**, if we count how many times we can bitwise shift **B** to the left while still staying under **A**, then we can quickly work out a chunk of the solution. All that's left is to start over with the remaining amount of **A** and repeat this process, adding the results to our answer (**ans**) as we go.

Of course, negative numbers will play havoc with our bitwise shifting, so we should first extract the **sign** difference and then use only positive numbers for **A** and **B**.

There's also the stated edge case, which only occurs at one permutation of **A** and **B**, so we can handle that at the outset.

####
*Implementation:*

*Implementation:*

Javascript and Python both handle numbers larger than **32-bit** internally, and Java requires only a small change to the conditions on its loops to avoid an issue.

C++, on the other hand, adheres strictly to the **32-bit** limit, so we have to define a few more edge cases to avoid exceeding these boundaries. That does allow us to simplify the code for both loops, however.

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var divide = function(A, B) {
if (A === -2147483648 && B === -1) return 2147483647
let ans = 0, sign = 1
if (A < 0) A = -A, sign = -sign
if (B < 0) B = -B, sign = -sign
if (A === B) return sign
for (let i = 0, val = B; A >= B; i = 0, val = B) {
while (val > 0 && val <= A) val = B << ++i
A -= B << i - 1, ans += 1 << i - 1
}
return sign < 0 ? -ans : ans
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def divide(self, A: int, B: int) -> int:
if A == -2147483648 and B == -1: return 2147483647
ans, sign = 0, 1
if A < 0: A, sign = -A, -sign
if B < 0: B, sign = -B, -sign
if A == B: return sign
while A >= B:
b = 0
while B << b <= A: b += 1
A -= B << b - 1
ans += 1 << b - 1
return -ans if sign < 0 else ans
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int divide(int A, int B) {
if (A == -2147483648 && B == -1) return 2147483647;
int ans = 0, sign = A > 0 == B > 0 ? 1 : -1;
if (A < 0) A = -A;
if (B < 0) B = -B;
if (A == B) return sign;
for (int i = 0, val = B; A - B >= 0; i = 0, val = B) {
while (val > 0 && A - val >= 0) val = B << ++i;
A -= B << i - 1;
ans += 1 << i - 1;
}
return sign < 0 ? -ans : ans;
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
int divide(int A, int B) {
int ans = 0, sign = A > 0 == B > 0 ? 1 : -1;
if (B == -2147483648) return A == B;
if (A == -2147483648)
if (B == 1) return -2147483648;
else if (B == -1) return 2147483647;
else A += abs(B), ans++;
A = abs(A), B = abs(B);
for (int i = 0; A >= B; i = 0) {
while (A >> i >= B) i++;
A -= B << i - 1, ans += 1 << i - 1;
}
return sign < 0 ? -ans : ans;
}
};
```

## Discussion (0)