[数据结构与算法]剑指offer-16 数值的整数次方

题目描述

实现?pow(x,?n)?，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
示例 3：

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

提示：

-100.0 <?x?< 100.0
-2^31?<= n <=?2^31-1
-10^4?<= x^n?<= 10^4

快速幂（二分法）：

? ? ? ? 当exp为偶数时，x^n=(x^2) ^ (n/2)

????????当exp为奇数时，x^n=(x^2)^(n/2) * x

当exp为负数时，先将其转换为long类型（防止溢出），exp= - exp，x=1/x

class Solution {
    public double myPow(double x, int n) {
        if(n==0)
            return 1.0;
        if(x==0)
            return 0.0;
        double result=1.0;
        long exp=n;
        if(exp<0)
        {
            exp=-exp;
            x=1/x;
        }
        while(exp>0)
        {
            if((exp&1)==1)
                result*=x;
            x*=x;
            exp=exp>>1;
        }
        return result;
    }
}