leetcode解题: Divide two Integers (29)

发表于 | 分类于

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

解法1：

这题有几个坑：一个是分母有可能是0， 这种情况要判断dividend的正负而返回。一个是INT_MIN/(-1) > INT_MAX, 所以这种条件下会overflow。还有一个是分子分母有可能符号不同。
除法的基本算法是把被除数A分拆成A = B*(2^n1 + 2^n2 + ….), 每一次找出比A小的最大的B的2的倍数，也就是求出Ni。这里每一次B乘以2的操作可以用左位移表示。
这里引出了另外一个坑，就是往左移的时候可能会溢出，所以一开始要把他们转化为long型再操作。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int divide(int dividend, int divisor) {
		if (divisor == 0) {
			return dividend >= 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
		}
		if (dividend == Integer.MIN_VALUE && divisor == -1) {
			return Integer.MAX_VALUE;
		}
		
		boolean neg = false;
	    if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
	        neg = true;
	    }
		int res = 0;
		long x = Math.abs((long)dividend);
		long y = Math.abs((long)divisor);
		while ( x >= y) {
			int shift = 1;
			while (x >= (y<<shift)) {
				++shift;
			}
			x -= y << (shift - 1);
			res += 1 << (shift - 1);
		}
		
		return neg ? 0 - res : res;         
    }
}