[力扣_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;
}