[力扣_29] 两数相除
题目入口:点击进入
前言:29和30题实不相瞒我想了一周,但是还是草草结尾,这道题尤为困难,因为位运算一直是自己的弱项,所以才琢磨良久,这题还是采用评论区大佬的思路,自己只能想到一点点门路。
相关算法:
- 位运算——时间复杂度O(logn),空间复杂度——O(1)
- 减法递增——时间复杂度O(logn),空间复杂度——O(1)
思路与算法:
题目表明了以下几个点:
- 不能使用取模,除法,乘法
- 只能存储32位整数的环境下进行
那么除了题目规定不能使用的运算,剩下的就只有:加减,左移,右移了,所以我们可以从这儿入手来解决,我们看个例子:10/3,在小时候是怎么做的呢?
3+3+3=9<10,这个时候还剩下一,显然加不上去了,那么就只能加3次,这是一个思路,就是让被除数每次减去除数,直到比除数小为止,但是,会超时,比如:
被除数为2^31,除数为2,那么我们将需要循环(2^31)/2,显然会超时的。
位运算
从上述思路我们可以得知,若使用位运算,则有<<和>>可以使用,我们来复习下这两个运算符:
- <<
- 左移一位,低位补0,也就是说,比如一个数8,二进制位1000,我们将其左移一位则变成了10000,那么增长为16
- >>
- 右移一位,高位补0,例如一个数8,二进制1000,我们将其右移一位变成0100,则为4
从上我们是不是可以得知,左移就等于乘了2,而右移是不是就等于除了2呢?我们再来模拟一下。拿10/3作例子,3的二进制为11,则将其不断左移:
- 3<<1=110=6
- 此时依旧小于10,我们将计数变量也左移一位,计数变量从1开始,原因是,3*1=3嘛,左移一位则变成10,也就是2
- 6<<1=1100=12
- 此时要大于10了,则肯定结果是不对的,但是我们可以发现,答案就在2与4之间
- 4是由结果继续右移得到的,但是此时不能右移。
- 这个时候怎么办?我们用10-6=4得到新的被除数,将除数恢复成3
- 继续去判断,4>3,但是3<<1=6,还是大于4了,所以我们只能返回一个1,也就是3本身,它比4要小,但是它的两倍比4要大
- 我们通过第一次的结果2加上第二次的结果1得到3
- 验证一下,10/3不考虑余数的情况下也等于3,则能证明我们上述的思路是正确的
归纳一下:
- 初始结果为1
- 因为若被除数比除数小,则直接就能在边界情况时返回0
- 判断除数<<是否大于被除数,若不大于,则将其右移动,直到它<<后的数大于被除数
- 结果也跟着<<
- 被除数减去此时最大的除数,恢复除数,重复1,2
- 返回结果
千言不胜一张图,我们看下图来了解,也就是我们小时候最常用的竖立乘法:
注意:我愚笨,这种解法只能解决不用规定的运算符,放出来也是为了更为了解运算在计算机里是如何实现的,这题因为int和边界的限制,在INT_MAX/2的样例中会报错,所以只能用long来实现。
代码如下所示:
long dive(long a,long b)//精髓所在,采用递归的思想
{
if(a<b) return 0;
long count=1;//若被除数比除数大,则初始化为结果为1
long c=b;
while(a>=(c<<1))
{
c=c<<1;
count=count<<1;
}
return count+dive((a-c),b);//结果累加
}
int divide(int dividend, int divisor){
//特判
if(dividend==divisor) return 1;//相等返回1,剪枝
if(divisor==1) return dividend;//若除数等于1则返回其本身
if(divisor==-1)//若除数等于-1.则对最小值要个判断,因为最小值若转换为最大值会越界
if(dividend <= INT_MIN) return INT_MAX;
else return -dividend;
int flag=0;
if(dividend>0&&divisor<0||dividend<0&&divisor>0) flag=1;
long divdtemp=dividend;
long divitemp=divisor;
if(dividend<0) divdtemp=-divdtemp;
if(divisor<0) divitemp=-divitemp;
long res=dive(divdtemp,divitemp);
if(flag) return 0-res;
return res;
}
减法模拟
位运算可以对原码进行,但是不能对补码进行!
位运算解法虽然可以解决问题,*但是达*****不到全部要求,我们来看边界条件:
为了方便记忆,我啰嗦一下,放上int的最大和最小值
-2147483648至+2147483647
这儿我们不提起复杂的计组知识,我们只需要知道:
若除数为-2147483648,我们使用位运算,必须将两数转换为正数来进行,但是若将这个数转换为正数,则越界了,所以在上种解法种,只能用long来存储。
竟然正数用不了,我们可否用负数来代替?但是负数又不能实现位运算,我们如何实现呢?想一下,左移是乘2,而不断加自己本身是否也是乘2呢?
- 3<<1=6
- 3+3=6
- 6<<1=12
- 6+6=12
诶,我们可以用自身相加来解决位移问题,那么我们来看如何解决边界问题。
我们从题意可知,其被除数和除数不会超过int的范围,那么我们可否将边界设为0
什么意思,我们可以拿INT_MIN=-2147483648减去每次的除数,来判断是否越界,若越界,则减去后肯定大于0,也就是说,只有除数每次倍增要大于或等于2147483648的时候,就达到了边界,则不继续了。
我们拿
这个例子来看
在第一次循环,其每次的被除数和结果倍增如下所示:
可以看到,我所框选的为此时的除数
它若再备增,则肯定超过了-2^31
我们若用-2^31去减去它,得到的数也就是超出的那一部分,但是是个正数,没有越界,可以用它来判断是否继续倍增
归纳一下:
- 用自身相加实现倍增,等同于乘2和左移
- 将被除数和除数转换为负数解决边界问题
- 每次判断其倍增的数与INT_MIN的差是否大于0
- 若不大于,则继续判断是否大于被除数(若大于,则未达到被除数,可以继续,若小于,则其不能继续)
- 上述两条件是与。
- 除数倍增,结果倍增
- 将被除数为被除数减去除数(负数相减即为相加,将除数恢复)
代码如下所示:
int dive(int a,int b)
{
if(b<a) return 0;//边界,因为是负数,则除数不能大于被除数
int count=1;//若不达到边界,则初始化为1
int c=b;
while(INT_MIN-(c+c)<0&&a<=(c+c))//精髓所在
{
c+=c;
count+=count;
}
return count+dive((a-c),b);
}
int divide(int dividend, int divisor){
//边界处理
if(dividend==divisor) return 1;
if(divisor==1) return dividend;
if(divisor==-1)
if(dividend <= INT_MIN) return INT_MAX;
else return -dividend;
int flag=0;//符号标记
if(dividend>0&&divisor<0||dividend<0&&divisor>0) flag=1;
int divdtemp=0;
int divitemp=0;
//全部转换为负数
if(dividend>0)
divdtemp=-dividend;
else
divdtemp=dividend;
if(divisor>0)
divitemp=-divisor;
else
divitemp=divisor;
//将负数递归
int res=dive(divdtemp,divitemp);
if(flag) return 0-res;
return res;
}