[leetcode] 29. Divide two numbers

29、 Divide two numbers

subject ：

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 [−2^31, 2 ^ 31 − 1]. In this question , If the division result overflows , Then return to 2^31 − 1.

Their thinking ：

 *  Their thinking ： This problem is division , So first popularize the word of division 
 *  merchant , Formula is ：( Divisor - remainder )÷ Divisor = merchant , Write it down as ： Divisor ÷ Divisor = merchant ... remainder , Is a mathematical term .
 *  In a division formula , Divisor 、 remainder 、 The relationship between divisor and quotient is ：( Divisor - remainder )÷ Divisor = merchant , Write it down as ： Divisor ÷ Divisor = merchant ... remainder ,
 *  And then deduce ： merchant × Divisor + remainder = Divisor .
 *
 *  Requestor , The first thing we think about is subtraction , How many times can it be reduced , Then how much is the quotient , But obviously subtraction is too inefficient 
 *
 *  Then we can use the displacement method , Because the computer is particularly efficient when doing displacement , Moving to the left 1 Equivalent to times 2, To the right 1 Equivalent to divided by 2
 *
 *  We can put one dividend（ Divisor ） Divide by 2^n,n The original for 31, Constantly decreasing n To test , When a n Satisfy dividend/2^n>=divisor when ,
 *
 *  It means that we have found a large enough number , The number of *divisor No more than dividend Of , So we can subtract 2^n individual divisor, And so on 
 *
 *  We can use 100/3 For example 
 *
 * 2^n yes 1,2,4,8...2^31 This number , When n by 31 when , This number is very large ,100/2^n It's a very small number , It must be less than 3 Of , So cycle down ,
 *
 *  When n=5 when ,100/32=3,  It happens to be greater than or equal to 3 Of , Then we will 100-32*3=4, That is to say, minus 32 individual 3, Next we will deal with 4, In the same way, you can subtract another 3
 *
 *  So the total is minus 33 individual 3, So business is 33
 *
 *  We have to deal with some special numbers , such as divisor It can't be for 0 Of ,Integer.MIN_VALUE and Integer.MAX_VALUE
 *

Reference code :

class Solution {
    
    public int divide(int dividend, int divisor) {
    
 if (dividend == 0) {
    
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
    
            return Integer.MAX_VALUE;
        }
        boolean negative;
        negative = (dividend ^ divisor) <0;// Use XOR to calculate whether the sign is different 
        long t = Math.abs((long) dividend);
        long d= Math.abs((long) divisor);
        int result = 0;
        for (int i=31; i>=0;i--) {
    
            if ((t>>i)>=d) {
    // Find a number that's big enough 2^n*divisor
                result+=1<<i;// Add... To the result 2^n
                t-=d<<i;// Subtract from the divisor 2^n*divisor
            }
        }
        return negative ? -result : result;// Reverse sign difference 
    }
}