首页 > 代码库 > Divide Two Integers
Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
分析：
不能用乘、除、取模运算，我们可以用的运算还有加、减、位运算。一个比较简单的想法是在dividend上不断减去divisor，知道余数小于divisor，然后减的次数就是所求结果。这里我们可以用类似binary search的方法用幂级跳跃试探dividend是divisor的多少倍，从而达到加速的目的。幂级跳跃又有两种方式，一种是dividend先减去divisor的1倍,另一种是dividend先减去比dividend小的divisor的最大倍数。由于乘2幂运算我们可以用位左移来实现，所以第二种方式要比第一种方式快，特别是dividend和divisor相差很多的时候。
Leetcode 通过版本：
class Solution {public: int divide(int dividend, int divisor) { long long div = (dividend > 0)? dividend:-(long long)dividend; long long dis = (divisor > 0)? divisor: -(long long)divisor; int result = 0; while(div >= dis){ int counter = 0; while(div >= dis<<counter){ counter++; } result += 1<<(counter-1); div -= dis<<(counter-1); } return ((dividend^divisor)>>31)?(-result):result; }};
超时版本：
class Solution {public: int divide(int dividend, int divisor) { long long div = (dividend > 0)? dividend:-(long long)dividend; long long dis = (divisor > 0)? divisor: -(long long)divisor; int result = 0; while(div >= dis){ long long c = dis; for(int i = 0; div >= c; i++, c<<i){ div -= c; result += 1<<i; } } return ((dividend^divisor)>>31)?(-result):result; }};
Divide Two Integers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。