这是力扣上的一道题目,难度为中等
@TOC
1、题目描述
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
在这里插入图片描述
2、题解效果
在这里插入图片描述
3、题解思路
举个栗子：11除以2
11先与2比大小，发现比2大，则将除数翻倍（加一次自己），结果1也翻倍，然后试试有没有比11大，不比11大就再翻倍，过程则变成（除数：2→4→8 结果1→2→4），到了除数为16时发现比11大了，就不要再翻倍了，除数依然设置成8且此时结果为4。
到这里时，再用11减去8，等于3，再去算3除以2的值，此时题目就变成了算3除以2，跟上面方法相同，算出来结果为1，此时题目变成1除以2，1小于2，结果为0。再把所有的结果加起来，4+1+0=5
在这里插入图片描述
再举个栗子：举个例子：11 除以 3 。
首先11比3大，结果至少是1， 然后让3翻倍，就是6。（结果也从1翻倍到2）
但发现11还是大于6，那我让这个6再翻倍，得12，11不比12大，吓死我了，差点让最小解2也翻倍得到4了。但是我知道最终结果肯定在2和4之间。也就是说2再加上某个数，这个数是多少呢？我让11减去刚才最后一次的结果6，剩下5，我们计算5是3的几倍，也就是除法，看，递归出现了。
在纸上画一画，模拟几遍就懂了，实在不行看代码吧！
4、代码
class Solution { public int divide(int dividend, int divisor) { if(dividend == 0) return 0;//0除以所有数为0 if(divisor == -1){ if(dividend>Integer.MIN_VALUE) return -dividend;// 只要不是最小的那个整数，都是直接返回相反数就好啦 return Integer.MAX_VALUE;// 是最小的那个，那就返回最大的整数啦 } int symFlag=1;//symFlag用于处理正负号的问题，如果两者同号，则为1，结果为正，异号，则为0，结果为负 long longDividend = dividend;//转为long型是因为部分测试用例很刁钻 long longDivisor= divisor; //把负的除数和负的被除数都转成正的便于计算，用symFlag处理正负号的问题 if(longDividend<0){ symFlag=-symFlag; longDividend=-longDividend; } if(longDivisor<0){ symFlag=-symFlag; longDivisor=-longDivisor; } if(symFlag<0) return -divideFunc(longDividend,longDivisor); else return divideFunc(longDividend,longDivisor); } public int divideFunc(long dividend,long divisor){ if(dividend<divisor) return 0; if(dividend==divisor) return 1; long tmpDivisor=divisor; long res=1; while(dividend>(tmpDivisor+tmpDivisor)){ res=res+res; tmpDivisor=tmpDivisor+tmpDivisor; } return (int)res+divideFunc(dividend-tmpDivisor,divisor); } }
