Implement pow(x, n).
由幂的关系Xn == Xn/2 * Xn/2,因此可以采用 二分思想计算.
先解决特殊值:
n == 0, 如果x == 0, 没意义，x != 0返回1n == 1, return xn == -1, 这个需要看x, 如果x != 0, return 1/x,如果x == 0无意义- 另外对于优化，当
x为0,1,-1时直接可以输出
对于|n| > 1的情况:
- 若n是奇数,
return x * pow(x, (n-1) / 2) * pow(x, (n-1) / 2); - 若n是偶数,
return pow(x, n / 2) * pow(x, n / 2);
- 当
n < 0, 可以递归调用1/pow(x, -n),但是当n == INT_MIN时，-n会溢出，因此应该先二分再处理负数情况，直到n == -1. - 浮点数在计算机中不能精确表示，因此不能直接通过
==比较，比如x == 0是错误的写法，应该写成fabs(x - 0) < ERROR,ERROR为误差,可以设置为1e-8
const double ERROR = 1e-8;
int doubleEQ(double x, double y)
{
return fabs(x - y) < ERROR;
}
double myPow(double x, int n)
{
if (n == 0) {
return 1;
}
if (n == 1)
return x;
if (n == -1) {
if (fabs(x - 0) < ERROR) { // x位0 1/0 没有意义
return INT_MAX;
}
return 1.0 / x;
}
if (doubleEQ(x, 0)){
return 0;
}
if (doubleEQ(x, 1)) {
return 1;
}
if (doubleEQ(x, -1)) {
if ((n & 0x1))
return -1;
else return 1;
}
if ((n & 0x1)) {
int mid = (n - 1) / 2;
double half = myPow(x, mid);
return half * half * x;
} else {
double half = myPow(x, n / 2);
return half * half;
}
}