剑指 Offer 16. 数值的整数次方

题目描述

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

解题思路

普通方式迭代计算n次，复杂度即为O(N)。

本题介绍一种快速幂算法，在常数时间内完成幂运算，它的核心是对n进行二进制分解。

x的n次方就可以表示如下：

复杂度分析

时间复杂度：O(1)，只需要计算32次
空间复杂度：O(1)

知识点

位运算，快速幂算法

代码

class Solution {
public:
    double myPow(double x, int n) {
        // 处理n为0和n为负数这两种特殊情况
        if (0 == n) {
            return 1.0;
        }
        long long int N = n;
        if (N < 0) {
            x = 1.0 / x;
            N = -N;            // 这里有个坑，如果n为最小的负数，改变符号会导致上溢
        }
        double res = 1.0;
        for (int i = 0; i < 32; ++i) {
            long long int digit = N & (1 << i);     // 与N相关的地方也要小心坑
            if (digit != 0) {
                res *= x;
            }
            x = x * x;
        }
        return res;
    }
};