首页 > 代码库 > Divide Two Integers
Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
方法一：暴力破解，不断用被除数减去除数，直至出现负数停止，铁定超时。
方法二：对方法一的改进，每次寻找 满足2k-1 * 除数 <= 被除数 < 2k * 除数第一个k，那么被除数直接减去 2k-1 个除数，同时积累商值，更新被除数
需要注意溢出的问题。
1 class Solution { 2 public: 3 int divide(int dividend, int divisor) { 4 bool minus = false; 5 if( (dividend>0 && divisor<0) || (dividend<0 && divisor>0) ) minus = true; //判断正负 6 long long divd = abs((long long)dividend); //防止溢出 7 long long divs = abs((long long)divisor); 8 long long ans = 0; 9 while( divd >= divs ) { //如果被除数依然大于除数，表明可以继续减10 long long tmp = divs;11 int i=0;12 while( tmp <= divd ) { //寻找第一个满足2k-1 * 除数 <= 被除数 < 2k * 除数的k13 tmp <<= 1;14 ++i;15 }16 ans += 1<<(i-1); //积累商值17 divd -= tmp>>1; //被除数更新18 }19 return minus ? -ans : ans;20 }21 };
方法三：二分搜索商值，可以确定商值在[0，被除数]之间，因此可以在这区间不断进行二分搜索，由于不能使用乘法，除法，取模操作，那么计算 商*除数的 运算修改为加、减、移位操作，即multic * num = multic 为偶数，multic/2 * num * 2 或 multic 为奇数，multic/2 * num * 2 + num，那么时间复杂度就为O(lognlogn)
1 class Solution { 2 public: 3 int divide(int dividend, int divisor) { 4 bool minus = false; 5 if( (dividend>0 && divisor<0) || (dividend<0 && divisor>0) ) minus = true; 6 long long divd = abs((long long)dividend); 7 long long divs = abs((long long)divisor); 8 long long ans = 0; 9 long long left = 0, right = divd; //确定搜索区间10 while( left <= right ) {11 long long mid = left + ( (right-left) >> 1 ); //取中12 long long tmp = multiple(mid, divs); //计算mid * 除数13 if( tmp == divd ) { //如果乘后的值等于被除数14 ans = mid;15 break;16 }17 if( tmp < divd ) { //如果乘后值小于，那么应该增大商18 ans = mid;19 left = mid+1;20 }21 else right = mid-1; //否则减少商22 }23 return minus ? -ans : ans;24 }25 26 long long multiple(long long multic, long long num) { //分治法求a*b27 if( multic == 0 ) return 0;28 long long ans = multiple(multic>>1, num) << 1; //先求a/2 * b，在将值乘229 if( multic & 1 ) ans += num; //如果a为奇数30 return ans;31 }32 };
Divide Two Integers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。