LeetCode - Medium - 29. Divide Two Integers

本是古典何须时尚 2023-01-07 07:17 105阅读 0赞

## Topic ##

*  Math

## Description ##

[https://leetcode.com/problems/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`.

**Note**:

*  Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: \[−2³¹, 2³¹ − 1\]. For this problem, assume that your function **returns 2³¹ − 1 when the division result overflows**.

**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.

**Example 3**:

Input: dividend = 0, divisor = 1
    Output: 0

**Example 4**:

Input: dividend = 1, divisor = 1
    Output: 1

**Constraints**:

*  \-2³¹ <= dividend, divisor <= 2³¹ - 1
 *  divisor != 0

## Analysis ##

方法一：我写的。

一开始，打算将被除数，除数绝对值后（先得出结果正负号），然后二分查找一个候选商，然后除数累加商值数，累加值与被除数相比，从而得出最佳候选商。但这方法在溢出情况处理很棘手，特别是被除数是`Integer.MIN_VALUE`情况（另外，`Integer.MIN_VALUE == Math.abs(Integer.MIN_VALUE)`为`true`，负数的绝对值还是负数，这情况是不允许的）。因此，放弃这种方法。

换种另一个角度，先得出结果正负号，让被除数，除数都是变成负数，然后让除数左移若干位，逼近被除数，逼近得差不多，得出半成商。接着就换成用加法逼近，得出最佳近似商。最后，根据一开始保留结果正负号，得出最佳近似商正负号，并将近似商返回。

--------------------

方法二 & 方法三：别人写的，简洁，优雅。

## Submission ##

public class DivideTwoIntegers { 
    
    	//方法一：我写的
    	public int divide(int dividend, int divisor) { 
    		if (divisor == 0)
    			throw new ArithmeticException();
    
    		if (dividend == Integer.MIN_VALUE && divisor == -1)
    			return Integer.MAX_VALUE;// 针对溢出情况
    
    		boolean negative = dividend > 0 ^ divisor > 0;
    
    		if (dividend > 0) dividend = -dividend;
    		if (divisor > 0) divisor = -divisor;
    
    		int quotient = 0, product = 0;
    
    		// 粗略得出商
    		for (int i = 0; i < 32; i++) { 
    			int temp = divisor << i;// 相当于divisor * 2的i次方
    
    			// temp >> i != divisor, 溢出情况
    			if (temp < dividend || temp >> i != divisor) { 
    				break;
    			} else if (temp > dividend) { 
    				product = temp;
    				quotient = 1 << i;
    			} else { 
    				return (negative ? -1 : 1) << i;
    			}
    		}
    
    		// 较精确逼近商
    		while (true) { 
    			int temp = product + divisor;
    			// temp > 0, 溢出情况
    			if (temp < dividend || temp > 0)
    				break;
    			product = temp;
    			quotient++;
    		}
    
    		return negative ? -quotient : quotient;
    	}
    
    	//方法二：
    	public int divide2(int A, int B) { 
    		if (A == Integer.MIN_VALUE && B == -1)
    			return Integer.MAX_VALUE;
    		int a = Math.abs(A), b = Math.abs(B), 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;
    	}
    
    	//方法三：
    	public int divide3(int A, int B) { 
    		if (A == Integer.MIN_VALUE && B == -1)
    			return Integer.MAX_VALUE;
    		int a = Math.abs(A), b = Math.abs(B), res = 0;
    		for (int x = 31; x >= 0; x--)
    			if ((a >>> x) - b >= 0) { 
    				res += 1 << x;
    				a -= b << x;
    			}
    		return (A > 0) == (B > 0) ? res : -res;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class DivideTwoIntegersTest { 
    
    	@Test
    	public void test() { 
    		DivideTwoIntegers obj = new DivideTwoIntegers();
    
    		assertEquals(3, obj.divide(10, 3));
    		assertEquals(-2, obj.divide(7, -3));
    		assertEquals(0, obj.divide(0, 1));
    		assertEquals(1, obj.divide(1, 1));
    
    		assertEquals(Integer.MAX_VALUE, obj.divide(Integer.MAX_VALUE, 1));
    		assertEquals(Integer.MIN_VALUE, obj.divide(Integer.MIN_VALUE, 1));
    		assertEquals(0, obj.divide(1, Integer.MIN_VALUE));
    		assertEquals(-1, obj.divide(-1, 1));
    
    		assertEquals(1, obj.divide(Integer.MAX_VALUE, Integer.MAX_VALUE));
    		assertEquals(Integer.MAX_VALUE, obj.divide(Integer.MAX_VALUE, 1));
    		assertEquals(-Integer.MAX_VALUE, obj.divide(Integer.MAX_VALUE, -1));
    		assertEquals(-Integer.MAX_VALUE, obj.divide(-Integer.MAX_VALUE, 1));
    		assertEquals(Integer.MAX_VALUE, obj.divide(-Integer.MAX_VALUE, -1));
    		assertEquals(0, obj.divide(1, Integer.MAX_VALUE));
    		assertEquals(0, obj.divide(1, -Integer.MAX_VALUE));
    		
    		for (int i = -100; i <= 100; i++) { 
    			for (int j = 1; j < 100; j++) { 
    				assertEquals(i / j, obj.divide(i, j));
    			}
    		}
    	}
    
    	@Test
    	public void test2() { 
    		DivideTwoIntegers obj = new DivideTwoIntegers();
    
    		assertEquals(3, obj.divide2(10, 3));
    		assertEquals(-2, obj.divide2(7, -3));
    		assertEquals(0, obj.divide2(0, 1));
    		assertEquals(1, obj.divide2(1, 1));
    
    		assertEquals(Integer.MAX_VALUE, obj.divide2(Integer.MAX_VALUE, 1));
    		assertEquals(Integer.MIN_VALUE, obj.divide2(Integer.MIN_VALUE, 1));
    		assertEquals(0, obj.divide2(1, Integer.MIN_VALUE));
    		assertEquals(-1, obj.divide2(-1, 1));
    
    		assertEquals(1, obj.divide2(Integer.MAX_VALUE, Integer.MAX_VALUE));
    		assertEquals(Integer.MAX_VALUE, obj.divide2(Integer.MAX_VALUE, 1));
    		assertEquals(-Integer.MAX_VALUE, obj.divide2(Integer.MAX_VALUE, -1));
    		assertEquals(-Integer.MAX_VALUE, obj.divide2(-Integer.MAX_VALUE, 1));
    		assertEquals(Integer.MAX_VALUE, obj.divide2(-Integer.MAX_VALUE, -1));
    		assertEquals(0, obj.divide2(1, Integer.MAX_VALUE));
    		assertEquals(0, obj.divide2(1, -Integer.MAX_VALUE));
    		
    		for (int i = -100; i <= 100; i++) { 
    			for (int j = 1; j < 100; j++) { 
    				assertEquals(i / j, obj.divide2(i, j));
    			}
    		}
    	}
    	
    	@Test
    	public void test3() { 
    		DivideTwoIntegers obj = new DivideTwoIntegers();
    		
    		assertEquals(3, obj.divide3(10, 3));
    		assertEquals(-2, obj.divide3(7, -3));
    		assertEquals(0, obj.divide3(0, 1));
    		assertEquals(1, obj.divide3(1, 1));
    		
    		assertEquals(Integer.MAX_VALUE, obj.divide3(Integer.MAX_VALUE, 1));
    		assertEquals(Integer.MIN_VALUE, obj.divide3(Integer.MIN_VALUE, 1));
    		assertEquals(0, obj.divide3(1, Integer.MIN_VALUE));
    		assertEquals(-1, obj.divide3(-1, 1));
    		
    		assertEquals(1, obj.divide3(Integer.MAX_VALUE, Integer.MAX_VALUE));
    		assertEquals(Integer.MAX_VALUE, obj.divide3(Integer.MAX_VALUE, 1));
    		assertEquals(-Integer.MAX_VALUE, obj.divide3(Integer.MAX_VALUE, -1));
    		assertEquals(-Integer.MAX_VALUE, obj.divide3(-Integer.MAX_VALUE, 1));
    		assertEquals(Integer.MAX_VALUE, obj.divide3(-Integer.MAX_VALUE, -1));
    		assertEquals(0, obj.divide3(1, Integer.MAX_VALUE));
    		assertEquals(0, obj.divide3(1, -Integer.MAX_VALUE));
    		
    		for (int i = -100; i <= 100; i++) { 
    			for (int j = 1; j < 100; j++) { 
    				assertEquals(i / j, obj.divide3(i, j));
    			}
    		}
    	}
    
    }

[https_leetcode.com_problems_divide-two-integers]: https://leetcode.com/problems/divide-two-integers/