Java [leetcode 29]Divide Two Integers

浏览数：224 / 时间：2015年06月08日

题目描述：

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

If it is overflow, return MAX_INT.

解题思路：

把除数表示为：dividend = 2^i * divisor + 2^(i-1) * divisor + ... + 2^0 * divisor。这样一来，我们所求的商就是各系数之和了，而每个系数都可以通过移位操作获得。

详细解说请参考：http://blog.csdn.net/whuwangyi/article/details/40995863

代码如下：

public class Solution {
    public int divide(int dividend, int divisor) {
		boolean flag = (dividend > 0 && divisor > 0)
				|| (dividend < 0 && divisor < 0);
		long absDividend = Math.abs((long) dividend);
		long absDivisor = Math.abs((long) divisor);
		long quotient = dividePositive(absDividend, absDivisor);
		if (flag && quotient > Integer.MAX_VALUE)
			return Integer.MAX_VALUE;
		return flag ? (int) quotient : -(int) quotient;
	}
	public long dividePositive(long dividend, long divisor) {
		if (dividend < divisor)
			return 0;
		long quotient = 1;
		long originalDivisor = divisor;
		while (dividend >= (divisor << 1)) {
			quotient <<= 1;
			divisor <<= 1;
		}
		return quotient + dividePositive(dividend - divisor, originalDivisor);
	}
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java [leetcode 29]Divide Two Integers