首页 > 代码库 > LeetCode-Divdend two Integers
LeetCode-Divdend two Integers
题目:
Divide two integers without using multiplication, division and mod operator.
思路分析
二分法.将除数不断增倍,而结果同样扩大两倍,直到除数的值大于被除数.然后再利用被除数减去除数最后增长到小于被除数的值，递归求出结果.
例如:123/4
4<123 4*2=8<123 8*2=16>123 16*2=32<123
32*2=64<123 64*2=128>123 故结果增长的值为64/4=16.
再利用123-64=59,再次递归求出结果,最后肯定能得出59/4=14，余数为3,3<4抛弃.
故最终值为16+14=30
代码:
1 public Solution{ 2 public: 3 long long interDivide(unsigned long long dividend, 4 unsigned long long divisor){ 5 if(dividend<divisor) return 0; 6 7 long long result=1; 8 unsigned long long tmp=divisor,left; 9 10 while(tmp<=dividend){11 left=dividend-tmp;12 tmp<<=1;13 14 if(tmp>dividend){15 break;16 }17 18 else{19 result<<=1;20 }21 }22 23 return result+interDivide(left,divisor);24 }25 26 int Divide(int dividend,int divisor){27 unsigned long long _dividend=abs((long long)dividend);28 unsigned long long _divisor=abs((long long)divisor);29 30 bool positive=((dividend>=0) && (divisor>0)) || ((dividend<=0) && (divisor<0));31 32 return positive?interDivide(_dividend,_divisor):(-1)*interDivide(_dividend,_divisor);33 34 }35 };
之所以用unsigned long long是为了防止溢出.
LeetCode-Divdend two Integers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。