[LeetCode]Divide Two Integers

题目链接

数值的问题很多时候我们都要考虑二分和位运算的解法，这道题也是一样的。既然我们要implement除法并且不能用*, /, %，那么显而易见我们应该用减法。那么我们不能每一次用被除数减去除数直到被除数小于除数，因为太慢了。首先我们可以考虑二分，比如 12 / 4，我们就可以考虑先计算12 / 8，然后12 / 4 = 2 * 12 / 8 + (12 % 8) / 4。也就是说每一次n / d，我们考虑n / 2d直到商为1为止，然后回溯看下一层回来的余数还能不能给结果加1，假设被除数是n，时间复杂度O(log n)，代码如下：

	class Solution {
	public:
	int divide(int dividend, int divisor) {
	if(dividend == INT_MIN && divisor == -1)return INT_MAX;
	if(!divisor)return INT_MAX;
	bool isNeg = (divisor < 0) ^ (dividend < 0);
	long above = dividend, below = divisor;
	above = abs(above);
	below = abs(below);
	if(above < below)return 0;
	return isNeg? -recursion(above, below).first: recursion(above, below).first;
	}
	private:
	pair<int, int> recursion(long dividend, long divisor)
	{
	if(divisor > dividend / 2)
	return {1, dividend - divisor};
	auto p = recursion(dividend, divisor * 2);
	int quotient = p.first + p.first + (p.second >= divisor? 1: 0);
	int reminder = p.second >= divisor? p.second - divisor: p.second;
	return {quotient, reminder};
	}
	};

view raw Divide Two Integers.cpp hosted with ❤ by GitHub

另一种方法，假设被除数为n，除数为m，那么我很需要求d，使得n = d * m。d可以表示为a0 * 2^0 + a1 * 2^1 + a2 * 2^2 + ... + ak * 2 ^ k, where ai = [0, 1]，我们只需要把ai都求出来即可。 根据之前的等式，我们有n = (a0 * 2^0 + a1 * 2^1 + a2 * 2^2 + ... + ak * 2 ^ k) * m = a0 * 1m  + a1 * 2m + a2 * 4m + ... + ak * 2^k * m，我们可以每次对除数乘以2，直到其正好再乘一次就大于除数了，假设当前除数为2^i * m，当前的d加上2^i即可，代表对应的ai为1。每次减去除数直到除数小于被除数，乘以2的操作我们用位运算就可以完成，时间复杂度O((log n)^2)，代码如下：

	class Solution {
	public:
	int divide(int dividend, int divisor) {
	if(dividend == INT_MIN && divisor == -1)return INT_MAX;
	if(!divisor)return INT_MAX;
	bool isNeg = (divisor < 0) ^ (dividend < 0);
	long above = dividend, below = divisor, res = 0;
	above = abs(above);
	below = abs(below);
	while(above >= below)
	{
	long temp = below, multiple = 1;
	while(above >= (temp << 1))
	{
	temp <<= 1;
	multiple <<= 1;
	}
	above -= temp;
	res += multiple;
	}
	return isNeg? -res: res;
	}
	};

view raw Divide Two Integers_2.cpp hosted with ❤ by GitHub