h**o
发帖数: 548 | 1 题目： Divide two integers without using multiplication, division and mod
operator.
应该是怎么做哪？leetcode 有个人气解答如下，但是我看不懂， 有谁给解释一下你怎
么做的？
int divide(int dividend, int divisor) {
long long a = abs((double)dividend);;
long long b = abs((double)divisor);
long long ret = 0;
while (a >= b) {
long long c = b;
for (int i = 0; a >= c; ++i, c <<= 1) {
a -= c;
ret += 1 << i;
}
}
return ((dividend^divisor)>>31) ? (-ret) : (ret);
} | o**f
发帖数: 76 | 2 Line 2/3 ignore sign of dividend/divisor.
Line 5 to 12 try to remove divisor (or multiple of
divisors) from dividend, until a becomes < b.
Note that line 8 c<<=1 is bit operation and so does
line 10 ret += 1 <
Line 14 check signs of dividend/divisor, if they are
same, return ret. Otherwise, return -1 * ret.
1 int divide(int dividend, int divisor) {
2 long long a = abs((double)dividend);;
3 long long b = abs((double)divisor);
4
5 long long ret = 0;
6 while (a >= b) {
7 long long c = b;
8 for (int i = 0; a >= c; ++i, c <<= 1) {
9 a -= c;
10 ret += 1 << i;
11 }
12 }
13
14 return ((dividend^divisor)>>31) ? (-ret) : (ret);
15 } | z****e
发帖数: 54598 | 3 public class Solution {
public int divide(int dividend, int divisor) {
// Start typing your Java solution below
// DO NOT write main() function
if(dividend == 0) return 0;
long a = Math.abs((long)dividend);
long b = Math.abs((long)divisor);
long[] result = div(a,b);
long r = ((dividend>0&&divisor<0)||(dividend<0&&divisor>0))?-result[
0]:result[0];
return (int)r;
}
private long[] div(long a, long b){
long[] r = new long[2];
if(a
r[0] = 0;
r[1] = a;
}else if(a==b){
r[0] = 1;
r[1] = 0;
}else{
long[] result = div(a>>1,b);
r[0] = result[0]<<1;
r[1] = result[1]<<1;
if((a&1)==1) r[1]+=1;
if(r[1]>=b){
r[0]+=1;
r[1]-=b;
}
}
return r;
}
} | h****g
发帖数: 105 | 4 最主要的思想就是如果你一个一个的去计算被除数里包含多少哥除数的话，在极端例子
下比如INT_MAX/1, 时间复杂度会很高。那么怎么做才能更快呢？就是让除数指数级的
自增（c<<1）,直到下一次double比被除数大为止。假设此时被除数b自增到c, 那么商
可以分为两部分，一部分是c里包含有多少个b，另一个是a-c里包含有多少个b。前者我
们已经用ret记录好了，后者可以重复第一步的步骤 | h**o
发帖数: 548 | 5 明白了。 谢谢大牛们。
请问我贴的方法 time complexity 是 [(log(dividend/divisor)]^2 吧。
【在 h****g 的大作中提到】
: 最主要的思想就是如果你一个一个的去计算被除数里包含多少哥除数的话，在极端例子
: 下比如INT_MAX/1, 时间复杂度会很高。那么怎么做才能更快呢？就是让除数指数级的
: 自增（c<<1）,直到下一次double比被除数大为止。假设此时被除数b自增到c, 那么商
: 可以分为两部分，一部分是c里包含有多少个b，另一个是a-c里包含有多少个b。前者我
: 们已经用ret记录好了，后者可以重复第一步的步骤
| h**o
发帖数: 548 | 6 明白了。 谢谢大牛们。
请问我贴的方法 time complexity 是 [(log(dividend/divisor)]^2 吧。
【在 h****g 的大作中提到】
: 最主要的思想就是如果你一个一个的去计算被除数里包含多少哥除数的话，在极端例子
: 下比如INT_MAX/1, 时间复杂度会很高。那么怎么做才能更快呢？就是让除数指数级的
: 自增（c<<1）,直到下一次double比被除数大为止。假设此时被除数b自增到c, 那么商
: 可以分为两部分，一部分是c里包含有多少个b，另一个是a-c里包含有多少个b。前者我
: 们已经用ret记录好了，后者可以重复第一步的步骤
| c********p
发帖数: 1969 | 7 你邮箱满了？
result[
【在 z****e 的大作中提到】
: public class Solution {
: public int divide(int dividend, int divisor) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(dividend == 0) return 0;
: long a = Math.abs((long)dividend);
: long b = Math.abs((long)divisor);
: long[] result = div(a,b);
: long r = ((dividend>0&&divisor<0)||(dividend<0&&divisor>0))?-result[
: 0]:result[0];
|
|
