不用/,*,mod乘、除、取模运算的除法

不用乘、除、取模运算，求两个整数的商。

思路一：

可以用一个循环来做。

思路二：

a/b=exp( log(a/b) )=exp( log(a) - log(b) )。

The tricky part of this question does not lie on the algorithm though. It has something to do with overflows. For particular, if we use Math.abs to compute the absolute value of Integer.MIN(-2147483648), we get -2147483648 again. So we should manually make it equal to Integer.MAX(2147483647). Most of the cases this is fine, except for one case where you try to divide Integer.MIN by 2, i.e., -2147483648 / 2 = -1073741824. However, 2147483647 / 2 = 1073741823. I have to add one more edge condition that if the divisor is 2, we just do the bitwise operation: right shift. Another node is Integer.MAX / Integer.MIN = 0 (not -1).

代码：

class Solution {
public:int divide(int dividend, int divisor) {if(divisor == 0)return 0;if(divisor == 1)return dividend;if(dividend == divisor)return 1;if(divisor == 2)return dividend >> 1;bool sign = false;if( (dividend > 0 && divisor < 0) ||(dividend < 0 && divisor > 0))sign = true;if(dividend == numeric_limits<int>::max() && divisor == numeric_limits<int>::min())return 0;dividend = dividend == numeric_limits<int>::min() ? numeric_limits<int>::max() : abs(dividend);divisor = divisor == numeric_limits<int>::min() ? numeric_limits<int>::max() : abs(divisor);int result = (int) floor(exp(log(dividend) - log(divisor)));return sign ? -result : result;}
};

不用/,*,mod乘、除、取模运算的除法

不用乘、除、取模运算，求两个整数的商。

思路一：

可以用一个循环来做。

思路二：

a/b=exp( log(a/b) )=exp( log(a) - log(b) )。

The tricky part of this question does not lie on the algorithm though. It has something to do with overflows. For particular, if we use Math.abs to compute the absolute value of Integer.MIN(-2147483648), we get -2147483648 again. So we should manually make it equal to Integer.MAX(2147483647). Most of the cases this is fine, except for one case where you try to divide Integer.MIN by 2, i.e., -2147483648 / 2 = -1073741824. However, 2147483647 / 2 = 1073741823. I have to add one more edge condition that if the divisor is 2, we just do the bitwise operation: right shift. Another node is Integer.MAX / Integer.MIN = 0 (not -1).

代码：

class Solution {
public:int divide(int dividend, int divisor) {if(divisor == 0)return 0;if(divisor == 1)return dividend;if(dividend == divisor)return 1;if(divisor == 2)return dividend >> 1;bool sign = false;if( (dividend > 0 && divisor < 0) ||(dividend < 0 && divisor > 0))sign = true;if(dividend == numeric_limits<int>::max() && divisor == numeric_limits<int>::min())return 0;dividend = dividend == numeric_limits<int>::min() ? numeric_limits<int>::max() : abs(dividend);divisor = divisor == numeric_limits<int>::min() ? numeric_limits<int>::max() : abs(divisor);int result = (int) floor(exp(log(dividend) - log(divisor)));return sign ? -result : result;}
};