2014
11-19

LeetCode-Divide Two Integers[模拟]

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

// LeetCode, Divide Two Integers
// 时间复杂度O(logn)，空间复杂度O(1)
class Solution {
public:
int divide(int dividend, int divisor) {
// 当 dividend = INT_MIN时，-dividend会溢出，所以用 long long
long long a = dividend >= 0 ? dividend : -(long long)dividend;
long long b = divisor >= 0 ? divisor : -(long long)divisor;

// 当 dividend = INT_MIN时，divisor = -1时，结果会溢出，所以用 long long
long long result = 0;
while (a >= b) {
long long c = b;
for (int i = 0; a >= c; ++i, c <<= 1) {
a -= c;
result += 1 << i;
}
}

return ((dividend^divisor) >> 31) ? (-result) : (result);
}
};


// LeetCode, Divide Two Integers
// 时间复杂度O(logn)，空间复杂度O(1)
class Solution {
public:
int divide(int dividend, int divisor) {
int result = 0; // 当 dividend = INT_MIN时，divisor = -1时，结果会溢出
const bool sign = (dividend > 0 && divisor < 0) ||
(dividend < 0 && divisor > 0); // 异号

// 当 dividend = INT_MIN时，-dividend会溢出，所以用 unsigned int
unsigned int a = dividend >= 0 ? dividend : -dividend;
unsigned int b = divisor >= 0 ? divisor : -divisor;

while (a >= b) {
int multi = 1;
unsigned int bb = b;
while (a >= bb) {
a -= bb;
result += multi;

if (bb < INT_MAX >> 1) { // 防止溢出
bb += bb;
multi += multi;
}
}
}
if (sign) return -result;
else return result;
}
};


Java代码:

public class Solution {
public static int divide(int dividend, int divisor) {
return (int)divideL(dividend,divisor);
}

public static long divideL(long dividend,long divisor){
if(divisor == 1) return dividend;
if(divisor < 0) return -divideL(dividend, -divisor);
if(dividend < 0) return -divideL(-dividend, divisor);
if(divisor > dividend) return 0;
if(divisor == 0) return Integer.MAX_VALUE;
long d = divisor;
long bitcnt = 1;
long ans = 0;
while(d < dividend ){
d <<= 1;
bitcnt <<= 1;
}
while(d >= divisor){
while(dividend >= d){
dividend -= d;
ans += bitcnt;
}
d >>= 1;
bitcnt >>= 1;
}
return ans;
}
}

1. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。