29. Divide Two Integers.md

title	toc	date	tags	top
29. Divide Two Integers	false	2017-10-30	Leetcode Math Binary Search	29

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

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: [$−2^{31}, 2^{31}−1$]. For the purpose of this problem, assume that your function returns $2^{31}−1$ when the division result overflows.

分析

找到除，最快的方法是使用二分查找，从0开始寻找到被除数。题目要求不能用乘除法，在使用二分查找的时候，使用加法循环达到乘法的效果。需要注意符号和溢出的问题。溢出的话，只有一种情况，就是-2146483648/-1这种情况，直接判断好了。

 public int divide(int dividend, int divisor) {
        // overflow
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }


        int flag = 1;
        // dividend < 0
        if (dividend < 0) {
            dividend = - dividend;
            flag = - flag;
        }

        // divisor < 0
        if (divisor < 0) {
            divisor = - divisor;
            flag = -flag;
        }
        int lo = 0, hi = dividend;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            int cmp = - dividend;
            // 计算 mid * divisor
            for (int i = 0; i < mid; i++) {
                cmp += divisor;
            }
            if (cmp < 0) lo = mid + 1;
            else if (cmp > 0) hi = mid - 1;
            else {
                if (flag == -1)
                    return -mid;
                return mid;
            }
        }

        if (flag == - 1)
            return 1 - lo;

        return lo - 1;
    }
    ```