c*******r 发帖数: 309 | 1 我看了下这题的code,看了半天没搞懂这里边的位移运算是在干嘛。 为啥不能直接
while loop里每次a-b然后count次数?
public int divide(int dividend, int divisor) {
// Start typing your Java solution below
// DO NOT write main() function
int a = Math.abs(dividend);
int b = Math.abs(divisor);
//b maybe Integer.MIN_VALUE
boolean neg = (dividend > 0 && divisor < 0) || (dividend < 0 &&
divisor > 0);
if (divisor == 0) {
return Integer.MAX_VALUE;
}
if (divisor == Integer.MIN_VALUE) {
if (dividend == Integer.MIN_VALUE) {
return 1;
}
else {
return 0;
}
}
if (dividend == Integer.MIN_VALUE) {
if (neg) {
return -1 + divide(dividend + b, b);
}
else {
return 1 - divide(dividend + b, b);
}
}
int product = b, result = 0;
while (a >= b) {
int q = 1;
while (a - product >= product) {
q = q << 1;
product = product << 1;
}
a = a - product;
product = b;
result += q;
}
if (!neg) {
return result;
}
else {
return -result;
}
}
} | s**x 发帖数: 405 | 2 while loop 太慢。你试试跑一个100000000/1 | m*****1 发帖数: 147 | | c*******r 发帖数: 309 | 4 int product = b, result = 0;
while (a >= b) {
int q = 1;
while (a - product >= product) {
q = q << 1;
product = product << 1;
}
a = a - product;
product = b;
result += q;
}
比较笨,这一段代码还是没看懂,向左位移应该每次是*2吧。这样如果是10/2的话,a=
10,b=2,最后q不是应该是8吧? | J**9 发帖数: 835 | 5 This is a speedy version of
while(a>=b)
{
a -= b;
count++;
}
Instead of counting it one by one, count it exponentially
1,2,4,8,....
Let's run it using 10/2:
a=10;
product=b=2;
outer loop 1:
q=1;
8>=2: ==> q=2; product = 4;
6>=4: ==> q=4; product = 8;
2>=8: inner loop stops
a=10-8=2;
product=2;
result = 4;
outer loop 2:
2>=2:
q=1;
2-2>=2: Inner loop never runs
a=2-2=0;
product = 2;
result = 4+1 = 5;
0>=2: outer loop stops
Done:
result = 5;
【在 c*******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : int product = b, result = 0; : while (a >= b) { : int q = 1; : while (a - product >= product) { : q = q << 1; : product = product << 1; : } : a = a - product; : product = b; : result += q;
| J**9 发帖数: 835 | 6 The same idea is also used in pow(a,b)
Similar idea is used in memcpy, memcmp, memset:
Instead of doing it byte by byte:
1) First do it long double (4 words) (or page if possible)
2) Then do it long (2 words)
3) Then do it word by word
4) For the last few bytes, do it byte by byte
Don't forget to do the typecast of pointers in each step.
【在 J**9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : This is a speedy version of : while(a>=b) : { : a -= b; : count++; : } : Instead of counting it one by one, count it exponentially : 1,2,4,8,.... : Let's run it using 10/2: : a=10;
|
|