# 29.Divide-Two-Integers

## 29. Divide Two Integers

## 题目地址

<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, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

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.
Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
```

## 代码

### Approach #1 Repeated Subtraction

```java
public int divide(int dividend, int divisor) {
    //Reduce the problem to positive long integer to make it easier.
    //Use long to avoid integer overflow cases.
    int sign = 1;
    if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
        sign = -1;
    long ldividend = Math.abs((long) dividend);
    long ldivisor = Math.abs((long) divisor);

    //Take care the edge cases.
    if (ldivisor == 0) return Integer.MAX_VALUE;
    if ((ldividend == 0) || (ldividend < ldivisor))    return 0;

    long lans = ldivide(ldividend, ldivisor);

    int ans;
    if (lans > Integer.MAX_VALUE){ //Handle overflow.
        ans = (sign == 1)? Integer.MAX_VALUE : Integer.MIN_VALUE;
    } else {
        ans = (int) (sign * lans);
    }
    return ans;
}

private long ldivide(long ldividend, long ldivisor) {
    // Recursion exit condition
    if (ldividend < ldivisor) return 0;

    //  Find the largest multiple so that (divisor * multiple <= dividend), 
    //  whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason.
    //  Think this as a binary search.
    long sum = ldivisor;
    long multiple = 1;
    while ((sum+sum) <= ldividend) {
        sum += sum;
        multiple += multiple;
    }
    //Look for additional value for the multiple from the reminder (dividend - sum) recursively.
    return multiple + ldivide(ldividend - sum, ldivisor); // 4 + 2 + 1
}
```

### Approach #2

This solution has `O(logN^2)` time complexity.

```java
public int divide(int A, int B) {
  if (A == 1 << 31 && B == -1) {
    return (1 << 31) - 1;
  }
  int a = Math.abs(A), b = Math.abs(B);
  int res = 0, x = 0;
  while (a - b >= 0) {
    for (x = 0; a - (b << x << 1) >= 0; x++);

    res += 1 << x;
    a -= b << x;
  }

  return (A > 0) == (B > 0) ? res: -res;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/array/29.divide-two-integers.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.