29. Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹,  2³¹ − 1]. For the purpose of this problem, assume that your function returns 2³¹ − 1 when the division result overflows.

---

要求不使用乘、除、取模运算求a除以b。马上想到用a不断减b，直到a<b为止，但是这种方法超时，因为当a很大，b很小时，要减很多次。有没有办法一次减很多个b呢，即一次性减b的t倍。但题目要求不能使用乘法，但是b每左移一位相当于b的2倍，所以可以用移位代替乘法。 我们知道任意一个自然数可以表示成以2的幂为底的一组基的线性组合，即 $$num=a_0*2^0+a_1*2^1+a_2*2^2+…+a_n*2^n$$ 如果我们能找到一个使得$2^n*b\leq a$的最大的$n$，则a可以一次性减掉$2^n$个b，速度就快很多了。 基于这个思想，我们每次找最大的n，然后$a-2^n*b$，不断循环，直到a<b。完整代码如下：

class Solution {
public:
    int divide(int dividend, int divisor)
    {
        if (divisor == 0)
            return INT_MAX;
        if (divisor == -1 && dividend == INT_MIN)
            return INT_MAX;
        unsigned int divd = dividend, divr = divisor;
        if (dividend < 0)
            divd = -divd; // 先都转换为正数，方便处理
        if (divisor < 0)
            divr = -divr;
        int ans = 0;
        while (divd >= divr) {
            unsigned long long tmp = divr; // 注意类型，防止溢出
            int p = 0;
            while (divd >= tmp) {
                tmp <<= 1;
                p++;
            }
            ans += 1 << (p – 1);
            divd -= divr << (p – 1);
        }
        int sign = dividend ^ divisor; // 首位为符号位，如果符号相同，异或之后为正数
        return sign >= 0 ? ans : -ans;
    }
};

本代码提交AC，用时8MS。
P.S.一直以来对数论的题都没底，这次在将负数转换为正数时也花了不少时间。

// (a)_2 = 1111 1111 1111 1111 1111 1111 1100 0010; (a)_10 = -62;
int a = -62;
// (b)_2 = 1111 1111 1111 1111 1111 1111 1100 0010; (b)_10 = 4294967234;
unsigned int b = a;
// (b)_2 = 0000 0000 0000 0000 0000 0000 0011 1110; (b)_10 = 62;
b = -b;

请看上面这个例子，当我们想把一个int转换为unsigned int时，如果是正数，直接强制类型转换没有问题，但是如果是负数，则会出问题。

我们知道一个数在内存中是以补码的形式保存的，把a强制类型转换为b，a,b在内存中的表示是一样的，只是此时b按unsigned int的格式来解析了，解析出来的结果自然不会是+62。
我们还知道负数的补码是对应正数补码取反加1，我们在将负数转换为正数的时候，同样的也是补码取反加1，所以还需要添加一句b = -b。

二刷。题目中说运行环境是32位系统，所以不能用long的类型，于是修改成如下代码。

class Solution {
public:
	int divide(int dividend, int divisor) {

		if (dividend == INT_MIN && divisor == -1)return INT_MAX;
		if (dividend == INT_MIN && divisor == 1)return INT_MIN;

		unsigned int a = dividend, b = divisor;
		if (dividend < 0)
			a = (~a+1);
		if (divisor < 0)
			b = (~b+1);

		int ans = 0;
		while (a >= b) {
			int p = 0;
			int tmp = b;
			while (a > tmp && tmp < INT_MAX / 2) {
				tmp <<= 1;
				++p;
			}
			if (p > 0) {
				ans += (1 << (p - 1));
				a -= (tmp >> 1);
			}
			else if (p == 0) {
				if (a >= tmp) {
					++ans;
					a -= tmp;
				}
			}
		}

		int sign = dividend ^ divisor;
		if (sign >= 0)return ans;
		else return -ans;
	}
};

最主要的改变是在while循环时，为了防止tmp左移过程中超过INT_MAX，可以在左移前判断它是否大于INT_MAX的一半，因为左移就是*2操作，如果左移之前已经大于INT_MAX的一半，则左移后肯定超过范围。

另外如果while时没有发生左移，则使用简单的减法操作。

最后由于不能用long，所以把所有数都转换为unsigned int，因为unsigned int能表示的正数范围比int大，即使是INT_MIN也能转换为正数的unsigned int存储。

本代码提交AC，用时4MS。