首页 > 代码库 > Divide Two Integers
Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
不用乘除法和取模运算去做除法,也就是说只能用加减和位运算,很自然的想法就是每次用被除数减去除数,得出减了多少次,就是结果,这样做在被除数很大除数很小的时候会超时,因此,在此基础上改进一下,每次把除数翻倍,再减,直到除数大于被除数,然后再每次将被除数除以2,做减法,直到被除数等于零,这样可以加速。这个过程中的翻倍和除以2都可以用位运算实现。
代码如下:
1 public int divide(int dividend, int divisor) { 2 int count = 0; 3 long a = Math.abs((long)dividend); 4 long b = Math.abs((long)divisor); 5 boolean isNegative = (dividend ^ divisor) >= 0; 6 long i = 1; 7 for (; a >= b; i<<=1, b <<= 1) { 8 a -= b; 9 count += i;10 }11 for (; i > 0; i>>=1, b >>= 1) {12 if (a >= b) {13 a -= b;14 count += i;15 }16 }17 return isNegative ? count : -count;18 }
AC 520ms
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。