【leetcode】29. Divide two numbers

subject ：

29.  Divide two numbers 
 Given two integers , Divisor  dividend  And divisor  divisor. Divide two numbers , Multiplication is not required 、 Division and  mod  Operator .
 Return dividend  dividend  Divide by divisor  divisor  Get the business .
 The result of integer division should be truncated （truncate） Its decimal part , for example ：truncate(8.345) = 8  as well as  truncate(-2.7335) = -2

 Example  1:

 Input : dividend = 10, divisor = 3
 Output : 3
 explain : 10/3 = truncate(3.33333..) = truncate(3) = 3

 Example  2:

 Input : dividend = 7, divisor = -3
 Output : -2
 explain : 7/-3 = truncate(-2.33333..) = -2
 
 Tips ：
 Both dividend and divisor are  32  Bit signed integer .
 The divisor is not  0.
 Suppose our environment can only store  32  Bit signed integer , The value range is  [−231,  231 − 1]. In this question , If the division result overflows , Then return to  231 − 1.

class Solution {
    
    /** *  Divide two numbers  * * @param dividend  Divisor  * @param divisor  Divisor  * @return  merchant （ Do not include decimals ） */
    public static int divide(int dividend, int divisor) {
    
        long result = 0;
        long x = dividend;
        long y = divisor;
        boolean negative = (x < 0 && y > 0) || (x > 0 && y < 0);

        if (x < 0) {
    
            x = -x;
        }
        if (y < 0) {
    
            y = -y;
        }
        //  because x/y The result must be [0,x] Within the scope of , So for x Use dichotomy 
        long left = 0;
        long right = x;
        while (left < right) {
    
            long mid = left + right + 1 >> 1;
            if (quickMulti(mid, y) <= x) {
    
                //  The multiplication result is not greater than x, Move the left pointer to the right 
                left = mid;
            } else {
    
                right = mid - 1;
            }
        }
        result = negative ? -left : left;

        //  Judge whether it overflows 
        if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) {
    
            return Integer.MAX_VALUE;
        }
        return (int)result;
    }

    /** *  Fast multiplication  * * @param a  The multiplier  * @param b  Multiplier  * @return  product  */
    public static long quickMulti(long a, long b) {
    
        long result = 0;

        while (b > 0) {
    
            if ((b & 1) == 1) {
    
                //  The current minimum is 1, Add in the result a
                result += a;
            }
            //  The multiplicand moves to the right 1 position , Equivalent to divided by 2
            b >>= 1;
            //  Multiplier multiplication , Equivalent to times 2
            a += a;
        }
        return result;
    }
}