leetCode-29-Divide-Two-Integers.md

题目描述（中等难度）

两个数相除，给出商。不能用乘法，除法和模操作。

本来觉得这道题蛮简单的，记录下自己的坎坷历程。

尝试1

先确定商的符号，然后把被除数和除数通通转为正数，然后用被除数不停的减除数，直到小于除数的时候，用一个计数遍历记录总共减了多少次，即为商了。

确定商的符号的时候，以及返回最终结果的时候，我们可能需要进行乘 -1 操作，即取相反数。而题目规定不让用乘法，所以我们需要知道计算机是怎么进行存数的。

计算机为了算减法，利用了同余的性质。

同余的定义是 a ≡ b ( mod m ) ，即 a mod m == b mod m ，例如 5 ≡ 17 mod ( 12 )。百度百科

同余有两个性质

反身性：a ≡ a ( mod m )；

同余式相加：若 a ≡ b ( mod m )，c ≡ d ( mod m )，则 a + c ≡ b + d ( mod m )；

现在我们进行模 16 的加法操作，先熟悉下下边的几个式子。

2 + 14 = 0

2 + （-3） = 15

5 + 15 = 4

重点来了！

计算 4 - 2 怎么算呢？

也就是 4 + （- 2）

4 ≡ 4（mod 16）

-2 ≡ 14（mod 16）

所以 4 + （- 2）= 4 + 14 = 2。

我们利用同余的性质，把减法成功转换成了加法，所以我们只需要在计算机里边将 -2 存成 14 就行了。我们这里减去 2 就等价于加上 14。

再比如 13 - 7 ，也就是 13 + （-7）

13 ≡ 13 （mod 16）

-7 ≡ 9（mod 16）

所有 13 + （- 7）= 13 + 9 = 6

我们成功把减 7 转换成了加上 9。

减 2 转换成加 14，减 7 转换成加 9，这几组数有什么联系呢？是的 2 + 14 = 16，7 + 9 = 16，他们相加通通等于 16，也就是我们取的模。有种互补的感觉，所以我们把 14 叫做 - 2 的补数，9 叫做 - 7 的补数。

可以看到，我们用一些正数表示了负数，总共有 16 个数，除去 0，还剩 15 个数，不可避免的是，这 16 个数，正数和负数的个数会相差 1，我们来看看是正数多，还是负数多。

补数	0	1	2	3	4	5	6	7	8
所代表的的数	0	1	2	3	4	5	6	7	等下
补数		15	14	13	12	11	10	9
所代表的数		-1	-2	-3	-4	-5	-6	-7

上边的列出的数，应该都没异议吧，那么正数多还是负数多呢？就取决于 8 代表多少了。

8 + 1 = 9 ，9 代表 -7 ，而 - 8 + 1 = - 7，所以 8 其实代表 - 8 。

所以 0 到 15 这 16 个数字可以表示的范围是 -8 ~ 7，-8 没有对称的正数。

我们再来看看计算机里是怎么存的，我们都知道，计算机中是以二进制的方式存储的。假设我们计算机能存储 4 位。范围就是 0000 到 1111，也就是 0 到 15。

补数	0	1	2	3	4	5	6	7
二进制表示	0000	0001	0010	0011	0100	0101	0110	0111
所代表的数	0	1	2	3	4	5	6	7
补数		15	14	13	12	11	10	9	8
二进制表示		1111	1110	1101	1100	1011	1010	1001	1000
所代表的数		-1	-2	-3	-4	-5	-6	-7	-8

我们利用这个表格，求几个例子。

2 - 3 = 2 + （-3）= 2 的补数 + - 3 的补数 = 0010 + 1101 = 1111

而看表格， 1111 代表的数就是 -1 ，从而我们用加法计算出了 2 - 3 = - 1。

-3 - 2 = （-3）+（-2）= -3 的补数 + -2 的补数 = 1101 + 1110 = 1011

我们可以看到 1101 + 1110 本来等于 1 1011 ，因为只存储 4 位，所以最高位被丢掉了，其实这就进行了取模的操作，减去了 16 。如果我们看所对应的十进制是怎么操作的， 1101 表示 13，1110 表示 14 ，13 + 14 = 27 ，如果是模 16 操作下，就是 11 ，而 11 就是上边的结果 1011，看表格它代表的数是 - 5，- 3 - 2 = - 5 ，没毛病。

而且我们发现用这种表示方式，所有的正数首位都是 0 ，负数的首位都是 1 ，我们可以这样想。

假设正数和负数的首位相同，假如首位都是 0。

那么比如 a = 0010 这个正数，如果我们去找它的相反数 b，也就是对应的负数。由假设可以知道，它的相反数的最高位也是 0。即 0xxx 的形式。为了使得 a 和它的相反数相加等于 0，我们必须使得相反数 b 的第 3 位是 1，即 0x10，才能使得第 3 位的和是 0。但这样的话，第 3 位产生了进位， b 的第 2 位也得是 1，所以 b 就成了 0110，但这样虽然使得最后 3 位的和变成了 0，但是第 1 位我们假设了它是 0，由于第 2 位产生的进位，这样 a 和 b 相加不是 0 了，产生矛盾。所以假设不成立。所以正数和负数的首位一定不同，如果首位 0 代表正数，那么负数的首位一定是 1。

接下来的问题，给出一个数我们总不能查表去看它的补码吧，我们如何得出补码？

对于正数，看表格，我们直接写原码就可以了，例如 7 就是 0111 。

负数呢？

我们之前讨论过，对于模 16 的话，- 2 的补码是 14，也就是 16 - 2。- 7 的补码是 9，也就是 16 - 7 = 9。

我们从二进制的方式看一下。

我们来求 - 2 的补码，用 16 - 2 = 1 0000 - 0010 = ( 1111 + 1 ) - 0010 = ( 1111 - 0010 ) + 1 = 1101 + 1 = 1110 。

为什么转换成 1111 减去一个数，因为用 1111 减去一个数，虽然是减法，但其实只要把这个数按位求反即可。也就是把 2， 0010 按位求反变成 1101，再加上 1 就是 -2 的补码形式了，「按位取反，末位加 1 」这个口诀是不是很熟悉，哈哈，这就是快速求补码的法则。但我们不要忘了它的本质，其实是用模长减去它，但是计算机并不会减法，而是巧妙的转换到了取反再加 1 。

逆过程呢？如果我们知道了计算机存了个数 1110，那么它代表多少呢？首先首位是 1 ，它一定是一个负数，其次它是怎么得来的呢？往上翻，其实是用 16 - 2 =1110 得到的，我们现在是准备求 2 ，用 16 减去它就可以了，也就是 16 - 1110 = 1 0000 - 1110 = （1111 + 1）- 1110 = （1111 - 1110） + 1 = 0010。巧了，依旧是按位取反，末位加 1。而 0010 就是 2，所以 1110 就代表 - 2。

综上，其实我们就是用原来的一部分正数（其实说它是正数也无非是我们自己定义的，想起一句话，数学就像一门宗教，你要么完全相信，要么完全不信，哈哈）表示了负数，而现在为了实现减法，我们把 1xxx 的不当做正数了，把它定义为负数，是的没有负号，但开头是 1 ，我们就说它是负数，再取个名字就叫补数吧（其实就是它代表的负数离它最近的一个和它同余的数，例如 - 3，和它同余的最近的正数就是 13 了，所以 -3 的补数就是 13），再利用余数定理，以及计算机高位溢出等效于求模的性质，巧妙的用取反以及加法实现了减法。

说了这么多，回到开头的部分，怎么不用乘法，来实现求相反数呢？

求 x 的相反数，我们用 0 减去 x 就行。也就是 x 的相反数 = 0 - x = 0 + ( - x ) = -x，-x 在计算机中怎么存的呢，存的是 -x 的补码，-x 的补码怎么求？把 x 按位取反，末位加 1 。Java 中就是 ~x + 1 了，此时所存的就是 x 对应的那个负数，即它的相反数了。

3 的相反数怎么求？这求什么求呀，添个负号就行了，-3 呀！但是计算机可没我们这么智能，它只存储 01，所以我们把 -3 的补码求出来存到计算机里就可以了。 即把 3 （0011） 按位取反，末位加 1，得到 1101 就是它的补码，我们然后把 1101 存到了计算机中，我们以为它是 13 ，但我们给计算机重新定义了规则，它是补码，首位就代表了它是负数，计算机根据规则（按位取反，末位加 1 ，再添个负号）把它又还原成了我们所理解的 - 3。从而我们不进行乘法，根据我们给计算机制定的规则，实现了求相反数。

public int divide(int dividend, int divisor) {
    int ans = 0;
    int sign = 1;
    if (dividend < 0) {
        sign = opposite(sign);
        dividend = opposite(dividend);
    }
    if (divisor < 0) {
        sign = opposite(sign);
        divisor = opposite(divisor);
    }
    while (divisor <= dividend) {
        ans = ans + 1;
        dividend = dividend - divisor;
    }
    return sign > 0 ? ans : opposite(ans);
}

public int opposite(int x) {
    return ~x + 1;
}

本来信心满满，结果 Wrong Answer。

为什么出错了？ -1247483648 这个数有什么特殊之处吗？

我们知道 int 是用 4 个字节存储，也就是 32 位，那它表示的范围是多少呢？有多少个正数呢？除了第 1 位是 0 固定不变，其它位可以取 0 也可以 取 1，所以是 $$2^{31}$$，但这样的话还就包括了 0 ，所以还得减去 1 个数。也就是 $$2^{31}-1=2147483647$$。那负数有多少个呢，同理除了第 1 位是 1 固定不变，其它位可以取 0 也可以取 1，所以是 $$2^{31}=2147483648$$ 个负数，所以所表示的范围就是 -2147483648 到 2147483647。和之前我们讨论的是一致的，负数比正数多 1 个。

算法中，我们首先对被除数 - 2147483648 取相反数，变成了多少呢？这个不好想，那我们看之前的例子，再模 16 的基础上，最小的负数 - 8 ，取相反数变成了多少，- 8 的补码 1000，按位取反，末位加1，0111 + 1 = 1000，又回到了 1000，所以依旧是 - 8。所以题目中的 - 2147483648 取相反数，依旧是 - 2147483648（有没有发现很神奇 - 2147483648 * - 1 依旧是 - 2147483648）。所以上边的算法中，由于被除数依旧是个负数，所以根本没有进 while 循环，所以直接返回了 0 。

尝试二

既然 - 2147483648 这么特殊，那我们对它单独判断吧，如果被除数是 - 2147483648，除数是 -1 ，我们就直接返回题目所要求的 2147483647 吧，并且如果除数是 1 就返回 - 2147483648。

public int divide(int dividend, int divisor) {
    int ans = 0;
    int sign = 1;

    if (dividend < 0) {
        sign = opposite(sign);
        dividend = opposite(dividend);
    }
    if (divisor < 0) {
        sign = opposite(sign);
        divisor = opposite(divisor);
    }
    //单独判断一下
    if (dividend == Integer.MIN_VALUE && divisor == 1) {
        return sign > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    }
    while (divisor <= dividend) {
        ans = ans + 1;
        dividend = dividend - divisor;
    }
    return sign > 0 ? ans : opposite(ans);
}

public int opposite(int x) {
    return ~x + 1;
}

接着意外又发生了，这次竟然是 Time Limit Exceeded 了。

尝试三

逛了逛 Discuss，由于我们每次只减 1 次除数，循环太多了，找到了解决方案。

我们每次减 1 次除数，我们其实可以每次减多次。比如 10 / 1 ，之前是 10 - 1 = 9，计数器加 1 变成 1，然后 9 - 1 = 8，计数器加 1 变成 2，然后 8 - 1= 7，计数器加 1 变成 3，直至减到 0 < 1，我们结束了循环。我们其实可以翻倍减， 减完 1 ，减 2 ，再减 4 ，在减 8，当然计数器也不能只加 1 了，减数是翻倍减的，所以计数器也会一直翻倍的加。这里肯定会遇到一个问题，比如 10 - 1 = 9，9 - 2 = 7，7 - 4 = 3，3 - 8 = -5 < 1，它就走出了 while 循环。但是 3 本来还可以减 3 次 1，所以我们只要再递归就可以了。再看 3 / 1 的商，然后把之前的计数器的值加上 3 / 1 的商就够了。

public int divide(int dividend, int divisor) {
    int ans = 1;
    int sign = 1;
    if (dividend < 0) {
        sign = opposite(sign);
        dividend = opposite(dividend);
    }
    if (divisor < 0) {
        sign = opposite(sign);
        divisor = opposite(divisor);
    }
    if (dividend == Integer.MIN_VALUE && divisor == 1) {
        return sign > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    }
    int origin_dividend = dividend;
    int origin_divisor = divisor; 
    //由于 ans 初始值是 1 ，所以如果被除数小于除数直接返回 0 
    if (dividend < divisor) {
        return 0;
    } 
    dividend -= divisor;
    while (divisor <= dividend) {
        ans = ans + ans;
        divisor += divisor;
        dividend -= divisor;
    }
    int a = ans + divide(origin_dividend - divisor, origin_divisor);
    return sign > 0 ? a : opposite(a);
}
public int opposite(int x) {
    return ~x + 1;
}

不是超时了，神奇的错误又出现了，

我们又看到了，-2147483648 的出现，当除数是它的时候，又出现了神奇的错误，那我们再单独判断一下除数是它，总该可以了吧，继续加上。

if(divisor == Integer.MIN_VALUE){
    return 0;
}

其他的错误又出现了

被除数是 -2147483648 ，咦？我们之前不是考虑了吗，不不不，我们只考虑了除数是 1 和 -1 的时候，所以这个问题其实我们一直没有解决。我们必须修改算法了，我们的算法开始的部分是不管三七二十一，通通转换成正数，而出现 -2147483648 的时候，它无法转换成正数，我们怎么该解决呢？

解法一

虽然感觉很投机取巧，但也是最直接的方法了，既然 int 存不了，那我通通用 long 存就行了吧，最后返回的时候看看是不是 int 不能表示的 2147483648，是的话按题目要求就返回 2147483647。

public int divide(int dividend, int divisor) {
    long ans = divide((long)dividend,(long)(divisor));
    long m = 2147483648L;
    if(ans == m ){
        return Integer.MAX_VALUE;
    }else{
        return (int)ans;
    }
}
public long divide(long dividend, long divisor) {
    long ans = 1;
    long sign = 1;
    if (dividend < 0) {
        sign = opposite(sign);
        dividend = opposite(dividend);
    }
    if (divisor < 0) {
        sign = opposite(sign);
        divisor = opposite(divisor);
    } 
    long origin_dividend = dividend;
    long origin_divisor = divisor;
    
    if (dividend < divisor) {
        return 0;
    } 
    
    dividend -= divisor;
    while (divisor <= dividend) {
        ans = ans + ans;
        divisor += divisor;
        dividend -= divisor;
    }
    long a = ans + divide(origin_dividend - divisor, origin_divisor);
    return sign > 0 ? a : opposite(a);
}
public long opposite(long x) {
    return ~x + 1;
}

时间复杂度：最坏的情况，除数是 1，如果一次一次减除数，那么我们将减 n 次，但由于每次都翻倍了，所以总共减了 log ( n ) 次，所以时间复杂度是 O（log （n））。

空间复杂度： O（1）。

解法二

上边的解法总归不够优雅，那么如何不用 long 呢？

负数比正数多一个，我们之前的思路是把负数变成正数，但由于最小的负数无法变成正数，所以出现了上边奇奇怪怪的问题。我们为什么不把思路转过来，把正数通通转为求负数呢？然后很多加法会变成减法，大于号随之也会变成小于号。

public int divide(int dividend, int divisor) {
		int ans = -1;
		int sign = 1;
		if (dividend > 0) {
			sign = opposite(sign);
			dividend = opposite(dividend);
		}
		if (divisor > 0) {
			sign = opposite(sign);
			divisor = opposite(divisor);
		}   
		
		int origin_dividend = dividend;
		int origin_divisor = divisor;
		if (dividend > divisor) {
			return 0;
		} 
		
		dividend -= divisor;
		while (divisor >= dividend) {
			ans = ans + ans;
			divisor += divisor;
			dividend -= divisor;
		}
    	//此时我们传进的是两个负数，正常情况下，它就返回正数，但我们是在用负数累加，所以要取相反数
		int a = ans + opposite(divide(origin_dividend - divisor, origin_divisor));
		if(a == Integer.MIN_VALUE){
			if( sign > 0){
				return Integer.MAX_VALUE;
			}else{
				return Integer.MIN_VALUE;
			}
		}else{
			if(sign > 0){
				return opposite(a);
			}else{
				return a;
			}
		}
	}
	public int opposite(int x) {
		return ~x + 1;
	}
}

时间复杂度和空间复杂度没有变化，但是我们优雅的实现了这个算法，没有借用 long 。

总

这道题看起来简单，却藏了不少坑。首先，我们用一次一次减造成了超时，然后我们用递归实现了加倍加倍的减，接着由于 int 表示的数的范围不是对称的，最小的负数并不能转换为对应的相反数，所以我们将之前的算法思路完全逆过来，正数边负数，大于变小于，还是蛮有意思的。