Description
https://leetcode.com/problems/dividetwointegers/
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:

Example 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^311].
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.

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
.

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:

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