此题面试时常有：

解答方法有以下三种：

1。 直接迭代求解，这个很简单，复杂度O(n)。

1。 分治法。复杂度 logn

此方法有点凹，原理是：a的n次方可以分别对应两种情况:

1。 n为偶数  那么 aⁿ= (a*a)^n/2 

2。n为奇数 那么  aⁿ=  a*a^n-1

代码如下：

int

 power(

int

 a ,

int

 n)

{

     

if

(n 

==

 

0

)

          

return

 

1

;

     

if

(n

&

1

)

          

return

 a

*

power(a,n

-

1

);

     

else

          

return

 power(a

*

a,n

>>

1

);

}

 

3.此方法复杂度为 n的二进制表示中最高位1的index

原理为：事先建立a的 2^m m为(0,x);的表。指导找到一个最小的x使得 n<2^X然后 利用a中二进制位的位置和个数信息得到最终结果

#define

 MAX 32

int

 my_pow(

int

 a,

int

 n)

{

    

if

 (a 

==

 

1

  )

    {

        

return

 

1

;

    }

    

if

 (n 

==

0

)

    {

        

if

 (a 

==

 

0

)

            

return

 

-

1

;

        

return

 

1

 ;

    }

    unsigned 

int

 table[MAX];

    table[

0

] 

=

 a; 

    

for

 (

int

 i 

=

 

1

;i

<

MAX 

&&

 i

<

n;i

++

)

    {

        table[i] 

=

 table[i

-

1

]

*

table[i

-

1

];

    }

    i 

=

 

0

;

    

int

 m 

=

 

1

;

    

while

 ( n

>>

i)

    {

        

if

(

1

&

n

>>

i)

            m 

=

 m 

*

table[i];

        i

++

;

    }

    

return

 m;

}