admin 管理员组

文章数量: 1086019

不用/,*,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乘除取模运算的除法

版权声明：本文标题：不用,*,mod乘、除、取模运算的除法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1687782972a140880.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。