[leetcode]Divide Two Integers

新博文地址：[leetcode]Divide Two Integers

 

Divide Two Integers

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

 不使用 乘法、除法、取余来计算除法，这道题在很多书中都有提及，比如面试金典中就有一道题要求只用加法来计算：减法、乘法、除法。其中它对除法的算法思想是，用迭代一个一个加被除数，直到》dividend，但是这无疑是个坑，比如当divideng = Integer.MAX_VALUE；divisor =1；必定会超时。

这道题的题干就给人隐约一种位运算的感觉，事实也的确如此

第一次我尝试用2分法，每一次将divisor * 2，迟早newDivisor * 2会大于dividend，

那么dividend就在[newDivisor ，2 * newDivisor]之间，然后继续从newDivisor开始逐个+ divisor，直到dividend，但是还是超时了.....

今早上突然想到这种2分法可以持续下去的。

接下来用2进制，简单讲一下：

比如dividend 用2进制的表示是1010100，divisor是11，我们一直将divisor * 2，当divisor达到1100000时，超过了dividend，再将其/2，即110000，记录叠加次数。

然后得到二者之差——100100，继续迭代刚才的做法，得到divisor为11000，得到差1100,。

继续刚才的迭代，得到divisor为1100，差为0（差<divisor）则结束。

public int divide(int dividend, int divisor) {
		long absDividend = Math.abs((long) dividend);
		long absDivisor = Math.abs((long) divisor);
		long count = 0, c = 1;
		while (absDividend >= absDivisor) {
			absDivisor <<= 1;
			c <<= 1;
			if (absDivisor >= absDividend) {
				if (absDivisor > absDividend) {
					absDivisor >>= 1;
					c >>= 1;
					absDividend -= absDivisor;
				}
				count += c;
				c = 1;
				if(absDividend == absDivisor){
					break;
				}
				absDivisor = Math.abs((long) divisor);
			}
		}
		return (int) ((dividend < 0 ^ divisor < 0) ? -count : count);
	}

 要注意溢出情况的考虑，因此将int类型都向上转型为long