# LeetCode: Divide Two Integers

## Description

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

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.

Example 1:

```Input: dividend = 10, divisor = 3
Output: 3
```

Example 2:

```Input: dividend = 7, divisor = -3
Output: -2
```

## Solution

This challenge need to handle corner overflow cases carefully.

### Note #1

We first notice that when `dividend eq MIN_INT` and `divisor eq -1`, the result will overflow since the integer range is [-(2^31), 2^31-1].

### Note #2

Another corner case is when `dividend` and `divisor` is different signed, we need to convert them to `abs` values.

According to Note #1, we can not use `abs` function directly, since `abs(MIN_INT)` will introduce overflow. So we convert `int` into `long long` data type, which will be safe for reversing the negative value into positive value.

``````long long a = abs((long long)dividend);
long long b = abs((long long)divisor);
``````

### The naive algorithm

Without multiplication, division, and mod operator, we could come out with a naive solution, we use `add` operator to test how many times `divisor` added into a sum, which less or equal to `dividend`.

``````long long cur = 0;
int result = 0;
while(cur + divisor <= dividend) {
cur += divisor;
result++;
}
``````

But this will be very slow, especially when `dividend` is very large value and `divisor` is small.

### The algorithm with bits operation

Bits operation could be used to time performance.

We observe that: when `(value>>i) / divisor = cnt`, we could get `(value/divisor) = (cnt<<i)`.

So we iterate each bits and accumulate to the final result:

``````#define MAX 2147483647
#define MIN (-2147483648)
class Solution {
public:
int divide(int dividend, int divisor) {
assert(divisor != 0);
if(dividend == MIN && divisor == -1) return MAX;
bool rev = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);
long long a = abs((long long)dividend);
long long b = abs((long long)divisor);
long long result = 0;

while(a >= b) {
long long c = b;
for(int i=0; a >= c; ++i, c <<= 1) {
a -= c;
result += (1 << i);
}
}

return rev ? (-result) : (result);
}
};
``````

A more understandable logic is, because an integer could be represented in 32 bits.

``````for (int i = 31; i >= 0; i--) {
if ((a >> i) >= b) {
a -= (b << i);
result += (1 << i);
}
}
``````
Last Updated on