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;
|
