剑指offer—面试题16:数值的整数次方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

题目规定不能使用库函数，马上想到了循环n次。每次乘以 base得到结果。

算法一：

    func myPow(_ x: Double, _ n: Int) -> Double {

        var res = 1.0
        
        for _ in 0..<n {
            res *= x
        }
        return res
    }

以为就这么简单啦？拿到上面的代码到力扣上面提交，很快就会报错，因为我们没有考虑到各种边界条件。这也是这道题目所要考察的地方。开发人员考虑边界条件。上面代码只考虑了 base、exponent都正常的情况。base、exponent为 0 或者是负数的情况都没有考虑到。

算法一改良版：

    func myPow(_ x: Double, _ n: Int) -> Double {
        if x == 0 && n < 0  {
            fatalError("参数输入有误")
        }
        if n == 0 {
            return 1
        }
        
        let m = (n > 0) ? n : -n
        var res = 1.0
        for _ in 0..<m {
            res *= x
        }
        return n > 0 ? res : 1/res
    }

改良版后的算法已经满足了我们的算法要求，能够得到正确的答案了，但是提交到力扣上还是会因算法的时间复杂度问题超时，所以我们还需要优化。

要求一个数值的n次方时，我们只需要对数值的n/2次方进行一次平方就能够得到。如数值的16次方，可以转换为数值8次方的平方，依次推出：8次方的需要4次方的平方。4次方需要的是2次方的平方。这样大大的降低了我们循环的次数。(PS:如果所求是奇次方，可以将exponent-1，转换为偶次方后再乘以 base)

算法二：

  func myPow(_ x: Double, _ n: Int) -> Double {
        if x == 0 && n < 0  {
            fatalError("参数输入有误")
        }
        
        if n == 0 {
            return 1
        }
        
        if n == 1 {
            return x
        }
        var n = n
        var x = x
        var res = 1.0
        
        if  n < 0 {
            n = -n
            x = 1/x
        }
        
        while n > 0 {
            if n & 1 == 1 {
                res *= x
            }
            print(res)
            n = n >> 1
            x *= x
        }
        return res
    }