• 难度： 中等
• 通过率： 27.2%
• 题目链接：https://leetcode-cn.com/problems/powx-n

题目描述

来源于 https://leetcode-cn.com/

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−2³¹, 2³¹ − 1] 。

解法：

不断地进行 x = x * x 可以产生 x^2, x^4, x^8, x^16, ...。而 x^(a+b) = x^a * x^b。另外任何一个 n 都可以写出 1 2 4 8 16 ... 中某些数的和，比如 6 = 2 + 4，因此 x^6 = x^2 * x^4。

因此从最低位开始判断 n 的每一位，当该位是 1 的时候，就在结果中乘上一个 x，并在循环中不断更新 x。

需要注意的几个问题：

1. n 为最小的负数的时候，因为需要把 n 转为正数，如果直接取反，整数会溢出。因此需要使用一个无符号的数来存储幂次。另外在取反的时候需要防止溢出。

exp = -(n+1);
exp = exp + 1;

2. 当底数为零的时候，指数不能为负数。因为当 n 为正的时候， 0^n = 0，0 取倒数就出错了。

class Solution {
public:
    double myPow(double x, int n) {
        double result = 1;
        unsigned int exp;

        if(n < 0){
            exp = -(n+1);
			exp = exp + 1;
        }else{
			exp = n;
		}

        while(exp){
            if(exp & 1){
                result *= x;
            }
            x = x * x;
            exp >>= 1;
        }

        if(n < 0){
            result = 1 / result;
        }
        return result;
    }
};

举个例子，假如希望求 5^62，也就是 5 的 62 次方。为了算法高效，一个原则就是不做重复的计算。

5^62 = 5^(32+16+8+4+2) = 5^32 * 5^16 * 5^8 * 5^4 * 5^2

不管指数是多少，都可以将其分解为 2 的倍数的和，因为任何整数都能够写成 2 进制的形式，比如 62 = 00111110B。

以上算法中，随着迭代 w 的值会变成 x, x^2, x^4, x^8,…，我们只需要在合适的时候让它和 ans 相乘即可。合适的时刻就是 N 的二进制表示的相应位上为 1 的时候，这里使用了右移，只需要判断最低位是不是 1 就好了。

对于负的幂次，可以先求正幂次的结果，然后取倒数。

这个算法时间复杂度为 O(logN) ，这里的 N 是指待求幂次的大小，因此这算法算是一个伪多项式算法。