leetcode-divide-two-integers

题目大意

　　https://leetcode.com/problems/divide-two-integers/

　　两个int的除法，要求不能用乘法，除法，模运算

题目分析

　　此题要利用移位操作，除数每次向左移1位，因此增长量为指数级。但要注意当被除数为INT_MIN，除数为-1时产生结果会溢出的情况。本题如果借助long能够方便地处理一些int的越界情况，但我的做法是加了很多的预判，因此没有用long。

代码

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) { // overflow case
			return Integer.MAX_VALUE;
		}
		if (dividend == 0) { // trivial case
			return 0;
		}
		if (dividend == Integer.MIN_VALUE && divisor == Integer.MIN_VALUE) { // both are int_min
			return 1;
		}
		if (divisor == Integer.MIN_VALUE) { // only divisor is int_min
			return 0;
		}
		boolean isNeg = true;
		if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
			isNeg = false;
		}
		if (divisor < 0) {
			divisor = 0 - divisor; // here, divisor is never gona overflow
		}
		int ans = 0;
		if (dividend == Integer.MIN_VALUE) { // only dividend is int_min
			dividend = Integer.MAX_VALUE - (divisor - 1);
			ans++;
		} else {
			if (dividend < 0) {
				dividend = 0 - dividend; // here, dividend is never gona overflow
			}
		}
		while (dividend >= divisor) {
			int shift = 0;
			while (dividend >= (divisor << shift)) {
				shift++;
				int v = divisor << (shift - 1);
				if(v > (Integer.MAX_VALUE - v)) {
					break;
				}
			}
			dividend -= divisor << (shift - 1);
			ans += 1 << (shift - 1);
 		}
		return isNeg ? (0 - ans) : ans;
    }
}