数值的整数次方

题目描述

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

• -100.0 < x < 100.0

• n 是 32 位有符号整数，其数值范围是 $[−2^{31}, 2^{31} − 1]$ 。

  链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof

题解

本来想挨着乘起来，但是会遇到“超出时间限制”的例子。

二分思想，通过循环$x=x^2$的操作，每次把幂从n降到$n/2$直至0，每次$n>>1$的过程中，若n末位为1，则$res*=x$。时间复杂度：$O(log_2n)$.

double myPow(double x, int n) {
        bool neg=(n<0?true:false);
        if(x==0||x==1)return x;
        long k=n>0?n:-1*long(n);
        //n=n>0?n:-n;溢出
        double res=1;
        while(k>0)
        {
            if(k&1)
                res*=x;
            x*=x;
            k>>=1;
        }
        if(neg)res=1.0/res;
        return res;
    }