问题：求解pow(x,n)

　　解题思路：

　　　　1.将n个x相乘，时间复杂度为O(n)

　　　　2.分治思想：

• 二进制数转化成10进制数的方法：二进制数为n = 2^k-1 * a_k  +  2^k-2 *a_k-1+....+ 2¹ * a₂+ 2⁰ * a_1;

　　　　所以可以将xⁿ=x ^{(2^K-1) * a_k + (2^k-2)*a_k-1+....(2^0)*a₁}

　　　　上式=(x ^{(2^K-1) * a_k} )* (x ^{(2^K-2) * a_k-1} )*.....*(x ^{(2^i-1) * a_i} )*....*(x ^{(2^0) * a₁} )

• 将求n个k相乘的问题转化为以下两个问题：

　　　　1.计算 x^{2^0+2^1+..2^k-1}

解决方法：

　　　　　　　　x=x²；

　　　　2.求二进制数ak到a1

　　　　　　　　 解决方法：

　　　　　　　　采用>>右移位运算符号:将十进制数的二进制数形式的最右边一位数删除，即n>>=1;

　　　　　　　　&与操作：判断最后一个数是否为1,若为1，则乘入返回的幂函数当中；

　　　　　　　   从最后一位数开始往前，如果判断第i位的二进制数不为0，则将第i位的x进行res*=xⁿ

　　　　3.代码清单 

int pow(int x,int n){
    int res = 1;
    while(n){
        if(n&1)//位运算判断最后一位是否为1
        　　res*= x;
        x*= x;
        n >>= 1;//删除二进制中的最后一位元素
    }
    return res;
}

 　　　　4.算法性能分析

                       将原来求n个x相乘的问题转化为求(log2ⁿ)个关于n的二进制变式，时间复杂度为O(log2ⁿ);