Leetcode t29: divide two numbers

Title Description

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.

Ideas

Because multiplication cannot be used in questions 、 Division and remainder operations , You can consider using the addition and subtraction method to calculate .

for example , consider 100/7=14… …2, have access to 100 Yes 7 To cut down , Until negative . however , That's inefficient , Consider subtracting multiple 7（ such as $2^i$ individual 7）, To improve computational efficiency .

You can do the following ：
$100-2^3\ast 7=100-56=44$,
$44-2^2\ast 7=44-28=16$,
$16-2^1\ast 7=2$,

because $2<7$, So the final remainder is 2, Divisor is $2^1+2^2+2^3=14$.

however , Consider special circumstances ：

1. The divisor is 0, Direct output 0.
2. The divisor is $-2^{31}$, And the divisor is -1, that , According to the meaning , Should return $2^{31}-1$

Code

    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;
        long t = Math.abs((long)dividend);
        long d = Math.abs((long)divisor);
        int result = 0;
        for(int i = 31; i >= 0; i--) {
    
        	if( (d<<i) <= t ) {
    
        		result += (1<<i);
        		t -= d<<i;
        	}
        }
        return negative ? -result : result;// Reverse sign difference 
    }