首页 > 代码库 > 每日算法之二十五:Divide Two Integers
每日算法之二十五:Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
不使用乘法、除法和求模运算求两个数相除。
class Solution { public: long long internalDivide(unsigned long long dividend,unsigned long long divisor) { if(dividend<divisor) return 0; int result = 1; unsigned long long temp = divisor,left; while(temp<=dividend) { left = dividend - temp; temp<<=1; if(temp>dividend) break; else result<<=1; } return result + internalDivide(left,divisor); } int divide(int dividend, int divisor) { unsigned long long _dividend = abs(static_cast<long long>(dividend)), _division = abs(static_cast<long long>(divisor)); bool flag = ((dividend<=0)&&(divisor>0))|| ((dividend>=0)&&(divisor<0)); return flag?(-1)*internalDivide(_dividend,_division):internalDivide(_dividend,_division); } };
简要分析,以87/4为例:4小于87,4左移一位变成8,计数左移一位变成2。8小于87,继续左移变成16,计数变成4.16小于87左移变成32,计数变成8。32小于87左移变成64,计数变成16。继续左移变成128大于87。87减去64 = 23。计数为16倍。用23继续上述步骤,知道
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。