【剑指offer】数值的整数次方

分析：采用快速幂

以求2的5次方为例，5的2进制为101，第一个1的权值是4，第二个1的权值是1，所以2的5次方可以表示为2^4*2^1，这样以来本来时间复杂度是O(N),现在时间复杂度变成了O(log N)

又以3的13次方为例，13的二进制为1101，第一个1权值是8，第二个1权值是4，第三个1权值是1，所以3的13次方可以表示为

3^8*3^4*3^1

#include <iostream>
#include <stdio.h>
#include <memory>
using namespace std;

class Solution
{
public:
    double Power(double n,int m)//快速幂
    {
        if(n==0)
            return 0.0;
        if(m==0)
            return 1.0;
        int flag=0;
        if(m<0)
        {
            m=abs(m);
            flag=1;
        }
        double s=1.0,x=n;
        while(m)
        {
            if(m&1)//判断m的最后一位是否为1
            {
                s*=x;
            }
            x*=x;
            m>>=1;//舍去m的最后一位
        }
        if(flag==1)
            return 1.0/s;
        return s;
    }
};