[LeeCode]-Divide Two Integers 不用乘除的除法运算
Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
方法:不断的减去被除数。要提高效率,就每次把除数翻倍。
注意:出现两个符号不一致的情况,如果变换符号,那么就要注意负最小值,变换符号溢出问题,需要用unsigned int。
class Solution {
public:
int divide(int dividend, int divisor) {
int ret=0;
//异号问题
bool sign=(dividend >0 && divisor<0) ||(dividend<0 && divisor>0);
dividend=dividend>0 ? dividend : -dividend;
divisor=divisor>0 ? divisor:-divisor;
while(dividend>=divisor){
int n=1;
int divisor_n=divisor;
while(dividend>=divisor_n){
dividend-=divisor_n;
ret+=n;
//翻倍
if(divisor_n<INT_MAX>>1){ //防止溢出
divisor_n+=divisor;
n+=n;
}
}
}
return sign?-ret:ret;
}
};