题目
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 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
解题
方法一：倍增乘法
思路一：使用long防止溢出
class Solution { public: int divide(int dividend, int divisor) { if(dividend==INT_MIN&&divisor==-1) return INT_MAX; long a=dividend; long b=divisor; int sign=1; if(a>0&&b<0||a<0&&b>0){ sign=-1; } a=a>0?a:-a; b=b>0?b:-b; long res=0; while(a>=b){ long count=1,tmp=b; while(tmp<=a-tmp){ tmp+=tmp; count+=count; } a-=tmp; res+=count; } return sign>0?(int)res:(int)-res; } };
思路二：转为负数进行运算
推荐！
因为负数的绝对值比正数大1，因此如果将负数转到正数将会有问题，将正数转到负数就不会出现问题
思路就是比如 dividend=15,divisor=2
为了防止溢出问题，都转为负数了，记录sign，最后转回去即可
但是注意如果 dividend=INT_MIN, divisor=1的时候,count最后也会达到INT_MAX，会溢出，为了防止溢出，count开始也设置为负数，为-1
class Solution { public: int divide(int dividend, int divisor) { if(dividend==INT_MIN&&divisor==-1) return INT_MAX; int sign=-1; if(dividend<0&&divisor<0||dividend>0&&divisor>0){ sign=1; } dividend=dividend<0?dividend:-dividend; divisor=divisor<0?divisor:-divisor; int res=0; while(divisor>=dividend){ int count=-1,tmp=divisor; while(tmp>=dividend-tmp){ tmp+=tmp; count+=count; } dividend-=tmp; res+=count; } return sign>0?-res:res; } };
