d*******d 发帖数: 2050 | 1 电面小题.
double power(double x, int n);
要求时间lg(n), 空间O(1); |
y*******g 发帖数: 6599 | |
B*******1 发帖数: 2454 | 3 What is your answer?
【在 d*******d 的大作中提到】 : 电面小题. : double power(double x, int n); : 要求时间lg(n), 空间O(1);
|
w*******e 发帖数: 1588 | 4 double power(double x, unsigned int n)
{
if (n == 0) return 1;
if (n == 1) return x;
int xsquare = x * x;
if (n % 2 == 1) // n is odd
{
return (x * power(xsquare, n / 2));
}
else // n is even
{
return power(xsquare, n / 2);
}
}
We can also write an iterative version, I think. |
g**********y 发帖数: 14569 | 5 凑热闹
public double power(double x, int n) {
if (n < 0) return 1.0/power(x, -n);
double r = 1.0, pow = x;
while (n > 0) {
if ( (1 & n) > 0 ) r *= pow;
n >>= 1;
pow *= pow;
}
return r;
} |
B*******1 发帖数: 2454 | 6 你这不是o(1) space的
【在 w*******e 的大作中提到】 : double power(double x, unsigned int n) : { : if (n == 0) return 1; : if (n == 1) return x; : : int xsquare = x * x; : if (n % 2 == 1) // n is odd : { : return (x * power(xsquare, n / 2)); : }
|
d*******d 发帖数: 2050 | 7 我跟火鸡做法相似。
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
r*******n 发帖数: 3020 | 8 double power(double x, int n){
if (n == 0) return 1;
if (n == 1) return x;
if (n % 2 == 0) return power(x*x, n/2);
else return(x*x, n/2)*x;
}
【在 d*******d 的大作中提到】 : 电面小题. : double power(double x, int n); : 要求时间lg(n), 空间O(1);
|
B*******1 发帖数: 2454 | 9 学习了。
谢谢。
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
B*******1 发帖数: 2454 | 10 空间O(1);?
【在 r*******n 的大作中提到】 : double power(double x, int n){ : if (n == 0) return 1; : if (n == 1) return x; : if (n % 2 == 0) return power(x*x, n/2); : else return(x*x, n/2)*x; : }
|
|
|
y*******g 发帖数: 6599 | 11 最好转成unsigned然后在shift
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
w*******e 发帖数: 1588 | 12 If n = 4, it seems to return 1. Should we fix the last line like this?
return r * pow;
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
w*******e 发帖数: 1588 | 13 Never mind, you are right as n will end up with 1 to carry the final pow
value.
【在 w*******e 的大作中提到】 : If n = 4, it seems to return 1. Should we fix the last line like this? : return r * pow;
|
w*******e 发帖数: 1588 | 14 Never mind, you are right as n will end up with 1 to carry the final pow
value.
【在 w*******e 的大作中提到】 : If n = 4, it seems to return 1. Should we fix the last line like this? : return r * pow;
|
D*******e 发帖数: 151 | 15 If can use recursion, this is simple. But the restriction of O(1) space
becomes meaningless. |
D*******e 发帖数: 151 | 16 Nice. But we also need to consider sign(x).
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
r*******n 发帖数: 3020 | 17 有什么好处?
谢谢
【在 y*******g 的大作中提到】 : 最好转成unsigned然后在shift
|
c****p 发帖数: 6474 | 18 没有必要吧。。负数的情况已经在第一行就排除了。
【在 y*******g 的大作中提到】 : 最好转成unsigned然后在shift
|
c****p 发帖数: 6474 | 19 怕最高位为1。
【在 r*******n 的大作中提到】 : 有什么好处? : 谢谢
|
a********1 发帖数: 750 | 20 理论上right shift of signed 是implementation dependent
【在 c****p 的大作中提到】 : 没有必要吧。。负数的情况已经在第一行就排除了。
|
|
|
c****p 发帖数: 6474 | 21 多数情况下都是做成算术右移吧。。。
【在 a********1 的大作中提到】 : 理论上right shift of signed 是implementation dependent
|
y*******g 发帖数: 6599 | 22 反正没坏处
【在 c****p 的大作中提到】 : 多数情况下都是做成算术右移吧。。。
|
d*******d 发帖数: 2050 | 23 电面小题.
double power(double x, int n);
要求时间lg(n), 空间O(1); |
y*******g 发帖数: 6599 | |
B*******1 发帖数: 2454 | 25 What is your answer?
【在 d*******d 的大作中提到】 : 电面小题. : double power(double x, int n); : 要求时间lg(n), 空间O(1);
|
w*******e 发帖数: 1588 | 26 double power(double x, unsigned int n)
{
if (n == 0) return 1;
if (n == 1) return x;
int xsquare = x * x;
if (n % 2 == 1) // n is odd
{
return (x * power(xsquare, n / 2));
}
else // n is even
{
return power(xsquare, n / 2);
}
}
We can also write an iterative version, I think. |
g**********y 发帖数: 14569 | 27 凑热闹
public double power(double x, int n) {
if (n < 0) return 1.0/power(x, -n);
double r = 1.0, pow = x;
while (n > 0) {
if ( (1 & n) > 0 ) r *= pow;
n >>= 1;
pow *= pow;
}
return r;
} |
B*******1 发帖数: 2454 | 28 你这不是o(1) space的
【在 w*******e 的大作中提到】 : double power(double x, unsigned int n) : { : if (n == 0) return 1; : if (n == 1) return x; : : int xsquare = x * x; : if (n % 2 == 1) // n is odd : { : return (x * power(xsquare, n / 2)); : }
|
d*******d 发帖数: 2050 | 29 我跟火鸡做法相似。
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
r*******n 发帖数: 3020 | 30 double power(double x, int n){
if (n == 0) return 1;
if (n == 1) return x;
if (n % 2 == 0) return power(x*x, n/2);
else return(x*x, n/2)*x;
}
【在 d*******d 的大作中提到】 : 电面小题. : double power(double x, int n); : 要求时间lg(n), 空间O(1);
|
|
|
B*******1 发帖数: 2454 | 31 学习了。
谢谢。
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
B*******1 发帖数: 2454 | 32 空间O(1);?
【在 r*******n 的大作中提到】 : double power(double x, int n){ : if (n == 0) return 1; : if (n == 1) return x; : if (n % 2 == 0) return power(x*x, n/2); : else return(x*x, n/2)*x; : }
|
y*******g 发帖数: 6599 | 33 最好转成unsigned然后在shift
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
w*******e 发帖数: 1588 | 34 If n = 4, it seems to return 1. Should we fix the last line like this?
return r * pow;
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
w*******e 发帖数: 1588 | 35 Never mind, you are right as n will end up with 1 to carry the final pow
value.
【在 w*******e 的大作中提到】 : If n = 4, it seems to return 1. Should we fix the last line like this? : return r * pow;
|
w*******e 发帖数: 1588 | 36 Never mind, you are right as n will end up with 1 to carry the final pow
value.
【在 w*******e 的大作中提到】 : If n = 4, it seems to return 1. Should we fix the last line like this? : return r * pow;
|
D*******e 发帖数: 151 | 37 If can use recursion, this is simple. But the restriction of O(1) space
becomes meaningless. |
D*******e 发帖数: 151 | 38 Nice. But we also need to consider sign(x).
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
r*******n 发帖数: 3020 | 39 有什么好处?
谢谢
【在 y*******g 的大作中提到】 : 最好转成unsigned然后在shift
|
c****p 发帖数: 6474 | 40 没有必要吧。。负数的情况已经在第一行就排除了。
【在 y*******g 的大作中提到】 : 最好转成unsigned然后在shift
|
|
|
c****p 发帖数: 6474 | 41 怕最高位为1。
【在 r*******n 的大作中提到】 : 有什么好处? : 谢谢
|
a********1 发帖数: 750 | 42 理论上right shift of signed 是implementation dependent
【在 c****p 的大作中提到】 : 没有必要吧。。负数的情况已经在第一行就排除了。
|
c****p 发帖数: 6474 | 43 多数情况下都是做成算术右移吧。。。
【在 a********1 的大作中提到】 : 理论上right shift of signed 是implementation dependent
|
y*******g 发帖数: 6599 | 44 反正没坏处
【在 c****p 的大作中提到】 : 多数情况下都是做成算术右移吧。。。
|
A**u 发帖数: 2458 | 45 学习了
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|
s*****k 发帖数: 18 | 46 精彩
【在 g**********y 的大作中提到】 : 凑热闹 : public double power(double x, int n) { : if (n < 0) return 1.0/power(x, -n); : double r = 1.0, pow = x; : while (n > 0) { : if ( (1 & n) > 0 ) r *= pow; : n >>= 1; : pow *= pow; : } : return r;
|