LeetCode高频题29. 两数相除

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目

互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！

你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

文章目录

LeetCode高频题29. 两数相除@[TOC](文章目录) 题目一、审题2个数字求和的进位信息：（a&b）<<1加法：不就是无进位求和值+进位c吗？不用减号-，求x的相反数怎么求？？位运算：取反+1就是求负a-b不用减号怎么求？用位运算乘法不用乘号怎么求？位运算：小学乘法怎么乘，咱们就怎么乘那么，不用加减乘除符号？如何求除法，这就比较难了，也是LeetCode题目要求的最终LeetCode测试：除法总结

题目

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

来源：力扣（LeetCode）

链接：/problems/divide-two-integers

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、审题

示例 1:

输入: dividend = 10, divisor = 3

输出: 3

解释: 10/3 = truncate(3.33333…) = truncate(3) = 3

示例 2:

输入: dividend = 7, divisor = -3

输出: -2

解释: 7/-3 = truncate(-2.33333…) = -2

提示：

被除数和除数均为 32 位有符号整数。

除数不为 0。

假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2**31 − 1]。本题中，如果除法结果溢出，则返回 2的31 − 1次方。

2个数字求和的进位信息：（a&b）<<1

a与b，再向左移1位就是ab求和的进位信息

加法：不就是无进位求和值+进位c吗？

下图，5+6，无进位加法就是异或（5^6）=x，这个是我们多次讲过的知识：

进位就是（a&b）<<1=c

x+c【x或上c】就是+的功能

这就是加法的本质：无进位加法结果x+进位信息c

要注意，你要是c一直不是0，则需要将x看做a，c看做b，继续a+b重复下去

比如：

下面俩数相加的进位c是=（a&b）<<1

俩数相加无进位信息，即异或a^b

因为c不是0

所以需要继续反复迭代相加

这样反复相加，反复相加，直到c=0，返回a结果

这就是不用加好+的加法，直接位运算搞定：

手撕代码

//加法：不就是无进位求和值+进位c吗？public static int addNum(int a, int b){int sum = 0;while (b != 0){//第一次必进sum = a ^ b; //先求无进位相加信息ab = (a & b) << 1;//进位c赋值给b，b用过了a = sum;//把a赋值sum，说不定b=0，a就是最终结果了}return a;//当b进位为0，则}

测试：

public static void test(){int a = 5;int b = 6;//求a+bint ans = addNum(a, b);System.out.println(ans);}public static void main(String[] args) {test();}

11

再次测试：

public static void test(){int a = 100;int b = 1000;//求a+bint ans = addNum(a, b);System.out.println(ans);}public static void main(String[] args) {test();}}

1100

如何？

不用加号做加法，就这么干，屌爆了不？？？

加减乘除的速度慢

不用减号-，求x的相反数怎么求？？位运算：取反+1就是求负

-号不用的话

取负怎么求呢？？

-x=x取反+1

计算机底层就这么搞

你撸代码试试就知道了

//**-x=x取反+1**public static int negNum(int x){return (~x) + 1;//取反加一就是求负x}

老牛逼了：

测试：

System.out.println(negNum(1));System.out.println(negNum(2));System.out.println(negNum(0));System.out.println(negNum(10000));

-1-20-10000

如何，牛逼吧？

a-b不用减号怎么求？用位运算

有了上述俩函数：addNum，negNum

一个加法，一个求负

岂不是很简单？

这不难吧？

a-b=a+(-b)

就非常容易了呗

//a-b=a+(-b)public static int minus(int a, int b){return addNum(a, negNum(b));//a+(-b)=a-b}

测试：

System.out.println(minus(a, b));System.out.println(minus(1, 1));System.out.println(minus(1000, 100));

0900

厉害吧？

乘法不用乘号怎么求？位运算：小学乘法怎么乘，咱们就怎么乘

比如：

56*27怎么求?

该乘乘，该进位的进位，反正加起来就是了

二进制数底层就是干的这事：

代码如何优雅地实现呢？？

（0）最开始：ans=0

（1）a向左移动0位，b向右移动0位，由于b低位是1，故实际乘法1a=a

所以ans+=1a

（2）a<<1，b>>1

相当于把b的各个数字弄过来，乘向左移动过了的a

咱们的目的就是想完成乘法，然后还把对应的位向左逐渐移动，这是乘法的本质

如果b的末尾是0，ans+=0，啥也不加，因为0a=0

（3）a<<1，b>>1，继续移位，目的就是乘法完成对位

仍然是相当于把b的各个数字弄过来，乘向左移动过了的a

咱们的目的就是想完成乘法，然后还把对应的位向左逐渐移动，这是乘法的本质

如果b的末尾是1，ans+=1a，如果b的末尾是0，啥也不加，因为0a=0

（4）a<<1，b>>1，继续移位，目的就是乘法完成对位——原理就是这样了，优雅地向左，向右移位，然后看b的末尾数字

仍然是相当于把b的各个数字弄过来，乘向左移动过了的a

咱们的目的就是想完成乘法，然后还把对应的位向左逐渐移动，这是乘法的本质

如果b的末尾是1，ans+=1a，如果b的末尾是0，啥也不加，因为0a=0

（5）a<<1，b>>1，继续移位，目的就是乘法完成对位——原理就是这样了，优雅地向左，向右移位，然后看b的末尾数字

仍然是相当于把b的各个数字弄过来，乘向左移动过了的a

咱们的目的就是想完成乘法，然后还把对应的位向左逐渐移动，这是乘法的本质

如果b的末尾是1，ans+=1a，如果b的末尾是0，啥也不加，因为0*a=0

如果一旦b=0，此时ans就是结果

这很好理解吧！！！

运用上面的addNum(a,b)函数，轻松利用ab的移位状况，来求乘法！！

撸代码试试：

//运用上面的addNum(a,b)函数，轻松利用ab的移位状况，来求乘法！！public static int multi(int a, int b){//（5）a<<1，b>>1，继续移位，目的就是乘法完成对位——原理就是这样了，优雅地向左，向右移位，然后看b的末尾数字//仍然是相当于把b的各个数字弄过来，乘向左移动过了的a//咱们的目的就是想完成乘法，然后还把对应的位向左逐渐移动，这是乘法的本质//如果b的末尾是1，ans+=1*a，如果b的末尾是0，啥也不加，因为0*a=0//如果一旦b=0，此时ans就是结果int ans = 0;while (b != 0){//最开始a<<0,b>>0if ((b & 1) == 1) ans = addNum(ans, a);//然后，每次都要移动了a <<= 1;b >>>= 1;//不带符号位}//一旦b=0，就是ansreturn ans;}

这我自己手撕的哦

System.out.println(multi(a, b));System.out.println(multi(1, 1));System.out.println(multi(1, 2));System.out.println(multi(2, 2));System.out.println(multi(100, 100));System.out.println(multi(100, -100));System.out.println(multi(-100, -100));

012410000-1000010000

绝对牛逼！！

那么，不用加减乘除符号？如何求除法，这就比较难了，也是LeetCode题目要求的

本题的求法：

情况是这样的，咱们正常求除法咋搞？？

a/b，我们其实要把a和b求绝对值|a|/|b|

至于符号嘛，看原来的ab，同为正，不同为负就行

比如：

但是这样有一个bug

因为系统最小值

Integer.MIN_VALUE=-2147483648，求得的绝对值，要比int范围大，因为

Integer.MAX_VLAUE=2147483647

public static void test2(){System.out.println(Integer.MIN_VALUE);System.out.println(Integer.MAX_VALUE);}

-21474836482147483647

所以呢，咱也表示不下系统最小

那么就分开单独讨论系统最小

那就是4种状况了

（1）a是Integer.MIN_VALUE，b也是Integer.MIN_VALUE，ans=1，没啥可说的

（2）a是正常值，b是Integer.MIN_VALUE，a竟然比b小，b太大，必然ans=0，正常系统除完就是0

（3）a和b都是正常值，求绝对值去做除法

（4）a是Integer.MIN_VALUE，b是正常值【很麻烦】

（1）a是Integer.MIN_VALUE，b也是Integer.MIN_VALUE，ans=1，没啥可说的

（2）a是正常值，b是Integer.MIN_VALUE，a竟然比b小，b太大，必然ans=0，正常系统除完就是0

举个例子：1/3=0,3/8=0,1/2=0

所以只需要看下面俩麻烦事：

（3）a和b都是正常值，求绝对值去做除法

除法就是乘法的逆运算：

比如下面的ans=bc

怎么算呢？

实际上ans=bk1+b*k2来的

k是2的幂次

对吧？

所以呢？

ans/b=c的c是咋求得？

（1）其实就让b往左移动，移动到接近ans，但是不超过ans时，移动了几位？c的那个位就是1

（2）然后ans-=b

（3）再倒回（1）去设置c，b恢复到原始那个b

最终c就是咱们的ans/b

b向左移动甲位的过程，实际上就是让b倍增，倍增到不超过a

剩下的部分实际上不就是：ans-b2的甲次方吗

也就是下图中的后面两项，把c的甲那个位设置为1

那你b从原始那个b开始向左移动，去逼近ans，这个ans实际上稍微就比b2的乙次方

把c的乙那个位设置为1

再把c的丙那个位设置为1

不就是ans/b，已经除尽了，但是又不会超过ans/b的结果吗？

比如5/2=2咋着这个c也是1 2 等等等的数

这个过程实现很简单的，记住一下

代码中，a一下子移动i=31位，然后看看a>=b吗？是的话，说明b能被a减掉，且c的i位可以设置为了，然后i–轮番干

至于转x和y目的就是为了控制符号，让他们都变绝对值ab再除

最后恢复正负号

x向右移动i位，且x>=y：等价于y向左移动到逼近x这个做法

所以手撕代码

//ab都是正常值的除法：public static int div(int a, int b){int x = a < 0 ? negNum(a) : a;int y = b < 0 ? negNum(b) : b;int ans = 0;//结果，就是c//中间x向右移动i位，且x>=y：等价于y向左移动到逼近x这个做法for (int i = 31; i >= 0; i = minus(i, 1)) {//每次移动i位if ((x >> i) >= y){//说明y逼近x但是不超过x//可以将c的i位设置为1，而且将此事x-y<<ix = minus(x, y << i);ans |= (1 << i);//不断设置ans的位，就是最终的除法结果，这个记住}}//最后看ab同号为正，不同号为负，不同号异或一定是1，同号异或为0return (a < 0) ^ (b < 0) ? negNum(ans) : ans;}

System.out.println(div(10, 1));System.out.println(div(10, 10));System.out.println(div(10, 100));System.out.println(div(-10, 10));System.out.println(div(-10, -10));System.out.println(div(10, -10));

1010-11-1

非常强大

（4）a是Integer.MIN_VALUE，b是正常值【很麻烦】

被除数a：dividend，除数b：divisior

首先a是系统最小值，b是(-1)得到：a/b= -系统最小，实际上就是系统最大+1，溢出了！！！

所以ans=系统最大，这是int的上界！！

如果b不是-1，就是正常值，a是系统最小，a/b咋算呢？？？

由于这个a实在是太大了，咱们把ab缩小来模拟一下

不妨设系统最小是-10，系统最大是9

因为系统最小比系统最大多1，我们就能直接定义这种int类型的数，OK？

没有为啥，就是这么规定的，就像系统当年规定那个2^31-1就是系统最大一样

我们就规定9就是系统最大，-10就是系统最小

这种情况下，a=-10，可不就是a为系统最小吗？b不妨设4，就是一个正常使用，这就是现在情况（4）遇到的情况，咋求？

这样搞，令ans=a+1再除b

相当于系统最小缩1，再除b

ans=-10+1再除4=-9/4=-2

你验证一下整个结果，是对的嘛？不是

因为-24=-8，不是-9，还缺啥呢？缺-1

缺这个值：-10-（-24）=-10+8=-2

再让这个-2/4=0

把它补给之前那个-2，就是-2，这就是-10/4的结果。

所以系统最小a/b是分两步走的，第一步，a+1/b=c，然后补一个【a-c*b】/b=d

结果就是c+d

再举例：

这就是系统最小a/b正常值的状况

手撕代码：

//系统最小a/b正常值的状况public static int sysLowestDivideByb(int a, int b){//a=Integer.MIN_VALUEif (b == negNum(1)) return Integer.MAX_VALUE;//b=-1时，a/b溢出了，上界//所以系统最小a/b是分两步走的，第一步，a+1/b=c，然后补一个【a-c*b】/b=d//结果就是c+dint c = addNum(a, 1) / b;//先借用除号验证一下，后面除号用div(a,b)替代哦int d = minus(a, multi(c, b)) / b;return addNum(c, d);}

上面的除号，我们先用真的/替代一下，一会求完a/b我们再回来替代，现在只是验证一下

System.out.println(sysLowestDivideByb(Integer.MIN_VALUE, -1));System.out.println(sysLowestDivideByb(Integer.MIN_VALUE, 1));System.out.println(sysLowestDivideByb(Integer.MIN_VALUE, 10));System.out.println(sysLowestDivideByb(Integer.MIN_VALUE, Integer.MIN_VALUE));

很OK

2147483647-2147483648-2147483641

绝对牛逼！！！

有了除法函数div，我们的a是系统最小就可以这样：

//系统最小a/b正常值的状况public static int sysLowestDivideByb(int a, int b){//a=Integer.MIN_VALUEif (b == negNum(1)) return Integer.MAX_VALUE;//b=-1时，a/b溢出了，上界//所以系统最小a/b是分两步走的，第一步，a+1/b=c，然后补一个【a-c*b】/b=d//结果就是c+dint c = div(addNum(a, 1), b);//先借用除号验证一下，后面除号用div(a,b)替代哦int d = div(minus(a, multi(c, b)) , b);return addNum(c, d);}

综合之后，我们的a/b就可以这么写了

//a/bpublic static int divide(int a, int b){//（1）a是Integer.MIN_VALUE，b也是Integer.MIN_VALUE，ans=1，没啥可说的//（2）a是正常值，b是Integer.MIN_VALUE，a竟然比b小，b太大，必然ans=0，正常系统除完就是0if (b == Integer.MIN_VALUE) return a == Integer.MIN_VALUE ? -1 : 0;//（4）a是Integer.MIN_VALUE，b是正常值【很麻烦】--单独处理if (a == Integer.MIN_VALUE) return sysLowestDivideByb(a, b);//（3）a和b都是正常值，求绝对值去做除法return div(a, b);}

这就是不用加减乘除中的除法运算

测试一把：

public static void test3(){System.out.println(divide(10, 1));System.out.println(divide(1, 10));System.out.println(divide(-1, 10));System.out.println(divide(10, -10));System.out.println();System.out.println(divide(Integer.MIN_VALUE, Integer.MIN_VALUE));System.out.println(divide(Integer.MIN_VALUE, 10));System.out.println(divide(Integer.MIN_VALUE, -1));System.out.println(divide(1, Integer.MIN_VALUE));}public static void main(String[] args) {// test();// test2();test3();}

1000-11-21474836421474836470

这就是除法！！

LeetCode这个题，算是super难度

你得知道加减乘除，不用加减乘除号，怎么搞

尤其是乘法怎么乘

除法又怎么除

考你的就是位运算的技巧

记住了！！！

最终LeetCode测试：除法

class Solution {//加法：不就是无进位求和值+进位c吗？public static int addNum(int a, int b){int sum = 0;while (b != 0){//第一次必进sum = a ^ b; //先求无进位相加信息ab = (a & b) << 1;//进位c赋值给b，b用过了a = sum;//把a赋值sum，说不定b=0，a就是最终结果了}return a;//当b进位为0，则结果就是a}//**-x=x取反+1**public static int negNum(int x){return (~x) + 1;//取反加一就是求负x}//a-b=a+(-b)public static int minus(int a, int b){return addNum(a, negNum(b));//a+(-b)=a-b}//运用上面的addNum(a,b)函数，轻松利用ab的移位状况，来求乘法！！public static int multi(int a, int b){//（5）a<<1，b>>1，继续移位，目的就是乘法完成对位——原理就是这样了，优雅地向左，向右移位，然后看b的末尾数字//仍然是相当于把b的各个数字弄过来，乘向左移动过了的a//咱们的目的就是想完成乘法，然后还把对应的位向左逐渐移动，这是乘法的本质//如果b的末尾是1，ans+=1*a，如果b的末尾是0，啥也不加，因为0*a=0//如果一旦b=0，此时ans就是结果int ans = 0;while (b != 0){//最开始a<<0,b>>0if ((b & 1) == 1) ans = addNum(ans, a);//然后，每次都要移动了a <<= 1;b >>>= 1;//不带符号位}//一旦b=0，就是ansreturn ans;}//系统最小a/b正常值的状况public static int sysLowestDivideByb(int a, int b){//a=Integer.MIN_VALUEif (b == negNum(1)) return Integer.MAX_VALUE;//b=-1时，a/b溢出了，上界//所以系统最小a/b是分两步走的，第一步，a+1/b=c，然后补一个【a-c*b】/b=d//结果就是c+dint c = div(addNum(a, 1), b);//先借用除号验证一下，后面除号用div(a,b)替代哦int d = div(minus(a, multi(c, b)) , b);return addNum(c, d);}//ab都是正常值的除法：public static int div(int a, int b){int x = a < 0 ? negNum(a) : a;int y = b < 0 ? negNum(b) : b;int ans = 0;//结果，就是c//中间x向右移动i位，且x>=y：等价于y向左移动到逼近x这个做法for (int i = 31; i >= 0; i = minus(i, 1)) {//每次移动i位if ((x >> i) >= y){//说明y逼近x但是不超过x//可以将c的i位设置为1，而且将此事x-y<<ix = minus(x, y << i);ans |= (1 << i);//不断设置ans的位，就是最终的除法结果，这个记住}}//最后看ab同号为正，不同号为负，不同号异或一定是1，同号异或为0return (a < 0) ^ (b < 0) ? negNum(ans) : ans;}public int divide(int dividend, int divisor) {//（1）a是Integer.MIN_VALUE，b也是Integer.MIN_VALUE，ans=1，没啥可说的//（2）a是正常值，b是Integer.MIN_VALUE，a竟然比b小，b太大，必然ans=0，正常系统除完就是0if (divisor == Integer.MIN_VALUE) return dividend == Integer.MIN_VALUE ? 1 : 0;//（4）a是Integer.MIN_VALUE，b是正常值【很麻烦】--单独处理if (dividend == Integer.MIN_VALUE) return sysLowestDivideByb(dividend, divisor);//（3）a和b都是正常值，求绝对值去做除法return div(dividend, divisor);}}

一绝吧

尤其乘法和除法，一定要搞清楚！！！

总结

提示：重要经验：

1）加法就是不带进位加法结果+进位信息c，不断迭代直到进位c=0结束

2）求负数，就是x取反再加1

3）减法，就是a+（-b）

4）乘法，用a向左移位，b向右移位，不断看b的末尾是0还是1，决定ans+=a还是0，直到最后b没了，为0，ans就是乘法结果

5）乘法的逆运算，让b左移k位，逼近a，不超过a，设置ans的k位为1，代码中，让a右移i位>=b的话，说明ans的i位可以设置为1，然后让a-b<<i位，最后搞定所有位，ans就是除法的结果，尤其除法，要讨论ab谁是系统最小的情况，还要看a是系统最小，b常数时的特殊除法。

3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。