## 整数相除

输入: dividend = 10, divisor = 3



输入: dividend = 7, divisor = -3



1. 被除数和除数均为 32 位有符号整数。

2. 除数不为 0。

3. 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31,  2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

## 数学的方式

### 解法

public int divide(int dividend, int divisor) {
double logAns = Math.log(Math.abs((double) dividend)) - Math.log(Math.abs((double) divisor));

}


### 性能

Runtime: 1 ms, faster than 100.00% of Java online submissions for Divide Two Integers.
Memory Usage: 36.9 MB, less than 42.42% of Java online submissions for Divide Two Integers.


### 解析

ln(A) - ln(B) = ln(A/B);


(dividend ^ divisor) < 0 则通过位运算，计算出对应的结果是正数还是负数。

## 逼近

### 例子

2^n是1，2，4，8…2^31这种数，当n为31时，这个数特别大，100/2^n是一个很小的数，肯定是小于3的，所以循环下来，

### java 实现

public int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}

long t = Math.abs((long) dividend);
long d = Math.abs((long) divisor);
int result = 0;

for (int i = 31; i >= 0; i--) {
//找出足够大的数2^n*divisor
if ((t >> i) >= d) {
//将结果加上2^n
result += 1 << i;
//将被除数减去2^n*divisor
t -= d << i;
}
}

//符号相异取反
return (dividend ^ divisor) < 0 ? -result : result;
}


### 性能

Runtime: 1 ms, faster than 100.00% of Java online submissions for Divide Two Integers.
Memory Usage: 36.8 MB, less than 57.77% of Java online submissions for Divide Two Integers.


## int 版本

### java 实现

public int divide(int A, int B) {
if (A == 1 << 31 && B == -1) return (1 << 31) - 1;
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;
}


>>>：无符号右移。无论是正数还是负数，高位通通补0。

### 效果

Runtime: 1 ms, faster than 100.00% of Java online submissions for Divide Two Integers.
Memory Usage: 36.7 MB, less than 70.20% of Java online submissions for Divide Two Integers.


## 参考资料

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

Clean-Java-solution-with-some-comment

No-Use-of-Long-Java-Solution