50. Pow(x, n)：

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

样例 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/2² = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹-1
• n 是一个整数
• -10⁴ <= xⁿ <= 10⁴

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 直接想到的就是模拟，x循环n - 1次乘以x，但是会非常慢。
• 还得是快速幂：xⁿ = x^{n / 2} * x^{n / 2}。
• 需要注意的一点是题目的参数n都是int / i32，一般就是32位有符号整数，有个坑，它的取值范围是【-2147483648，2147483647】，所以如果传参是 -2147483648，直接取反就悲剧了。

#include <iostream>

int main() {
    int n = INT_MIN;
//    -2147483648
//    -2147483648
//    2147483648
    std::cout << n << std::endl << -n << std::endl << -(long)n;
    return 0;
}

题解：

rust：

impl Solution {
    pub fn my_pow(x: f64, n: i32) -> f64 {
        fn quickMul(mut x: f64, mut n: i64) -> f64 {
            let mut ans = 1.0;
            // 在对 N 进行二进制拆分的同时计算答案
            while n > 0 {
                if n & 1 == 1 {
                    // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    ans *= x;
                }
                // 将贡献不断地平方
                x *= x;
                // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                n >>= 1;
            }
            return ans;
        }

        return if n >= 0 {
            quickMul(x, n as i64)
        } else {
            1.0 / quickMul(x, -(n as i64))
        }
    }
}

go：

func myPow(x float64, n int) float64 {
    quickMul := func(x float64, n int) float64 {
		ans := 1.0
		// 在对 N 进行二进制拆分的同时计算答案
		for n > 0 {
			if n&1 == 1 {
				// 如果 N 二进制表示的最低位为 1，那么需要计入贡献
				ans *= x
			}
			// 将贡献不断地平方
			x *= x
			// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
			n >>= 1
		}
		return ans
	}

	if n >= 0 {
		return quickMul(x, n)
	} else {
		return 1.0 / quickMul(x, -n)
	}
}

c++：

class Solution {
private:
    double quickMul(double x, long long n) {
        double ans = 1.0;
        // 在对 N 进行二进制拆分的同时计算答案
        while (n > 0) {
            if (n & 1 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x;
            }
            // 将贡献不断地平方
            x *= x;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            n >>= 1;
        }
        return ans;
    }
public:
    double myPow(double x, int n) {
        return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -(long)n);
    }
};

python：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quick_mul(x, n):
            ans = 1.0
            # 在对 N 进行二进制拆分的同时计算答案
            while n > 0:
                if n & 1 == 1:
                    # 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    ans *= x
                # 将贡献不断地平方
                x *= x
                # 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                n >>= 1
            return ans

        return quick_mul(x, n) if n >= 0 else 1.0 / quick_mul(x, -n)

java：

class Solution {
    public double myPow(double x, int n) {
        return n >= 0 ? quickMul(x, n) : 1.0 / quickMul(x, -(long)n);
    }

    private double quickMul(double x, long n) {
        double ans = 1.0;
        // 在对 N 进行二进制拆分的同时计算答案
        while (n > 0) {
            if ((n & 1) == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x;
            }
            // 将贡献不断地平方
            x *= x;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            n >>= 1;
        }
        return ans;
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~