 Coder's Cat

2020-02-02

## 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:

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^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.

### 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.