### 题目

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

If it is overflow, return MAX_INT.

### 暴力减法

1. 0不能当除数
2. 0除以任何数等于0
3. int不能表示2147483648,所以-2147483648/-1会溢出。

#### 代码

public class Solution {
public int divide(int dividend, int divisor) {
if (divisor == 0) { return Integer.MAX_VALUE; } // 0不能当除数
if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } // int不能表示2147483648
if (dividend == 0) { return 0; } // 0除以任何数等于0
int sign = (Integer.signum(dividend)== Integer.signum(divisor))? 1:-1; // get the sign
int dividendAbs = Math.abs(dividend);
int divisorAbs = Math.abs(divisor);
int times = 0;
while (true) {
dividendAbs = dividendAbs - divisorAbs;
if (dividendAbs >= 0) {
times++;
} else {
break;
}
}
return (sign==1)? times : -times;
}
}


### 用位移操作

10不断乘以2，来逼近被除数110。结果最多可以左移3位，说明110至少是108倍。

10 << 0 == 10  < 110
10 << 1 == 20  < 110
10 << 2 == 40  < 110
10 << 3 == 80  < 110
-------------------------- 停住
10 << 4 == 160 > 110

110 - 10 << 3 = 30
result = result + 1 << 3 = 8


10 << 0 == 10  < 30
10 << 1 == 20  < 30
-------------------------- 停住
10 << 2 == 40  > 30

30 - 10 << 1 = 10
result = result + 1 << 1 = 8 + 2 = 10


10 << 0 == 10  == 10
-------------------------- 停住
10 << 1 == 20  > 10

10 - 10 << 0 = 0
result = result + 1 << 0 = 10 + 1 = 11


edge case和符号处理这两个简化问题的手段，和第一种方法相同。

#### 代码

public class Solution {
public int divide(int dividend, int divisor) {
// edge case
if (divisor == 0) { return Integer.MAX_VALUE; } // 0不能当除数
if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } // int不能表示2147483648
if (dividend == 0) { return 0; } // 0除以任何数等于0
// treat sign
int sign = (Integer.signum(dividend)== Integer.signum(divisor))? 1:-1; // get the sign
// division
int result = 0;
long dividendL = Math.abs((long)dividend), divisorL = Math.abs((long)divisor);
while (dividendL >= divisorL) {
int shift = 1;
while (dividendL >= (divisorL << shift)) { shift++; }
result += 1 << (shift-1);
dividendL -= (divisorL << shift-1);
}
return (sign == 1)? result : -result;
}
}