Pow(x, n)
Problem statement:
Implement pow(x, n).
Solution 1: Log method.
We can write the problem statement as y = x^n, so let both sides become log(y) = log(x^n). Then we could have log(y) = nlog(x), futher transformation we could have elog(y) = y = enlog(x).
So we just need to compute enlog(x).
Code implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
double myPow(double x, int n) {
double absx = abs(x);
int absn = abs(n);
bool neg = false;
if (x < 0) {
neg = (n % 2 != 0);
}
bool inverse = (n < 0);
double abs_res = std::exp(absn * std::log(absx));
double result = abs_res;
if (neg) result = -result;
if (abs(result) == 0) return 0.0;
if (inverse) result = 1.0 /result;
return result;
}
};
|
Solution 2: Binary Representation
We know that any decimal number can be expressed as a polynomial of binary numbers. It means x^n can be represented as x^(a0*2^0 + a1*2^1 + a2 * 2^2 + ... + ak * 2^k), where ai can be either 0 or 1. Truely the ai values are just the binrary representation of N.
Given N = 12 as an example, its binary representaion is 1100. So x^12 can be rewritten as x^(2^3 + 2^2), by product of power property this can also be rewritten as x^(2^3) * x^(2^2).
x^(2^i) can be easily obtained as we move along with each bit of N's binary representation. If ith bit of N's binary representation is 1 we need to multiply the current x^(2^i) to the result.
Code implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
double myPow(double x, int n) {
if (n < 0) {
x = 1/x;
}
double result = 1;
unsigned int absn = abs(n);
while (absn) {
if (absn & 0x1) result *= x;
x *= x;
absn >>= 1;
}
return result;
}
};
|
No comments:
Post a Comment