【算法】求n的m次方（快速幂取模）

题目

求n的m次方，n，m均为自然数。

解析

看似简单的题目，但是要想写的高效还不是那么容易想出来。

实现

unsigned int power(unsigned int a, unsigned int n)
{
    unsigned int i, s;
    if (!n) return 1;
    if(!a) return 0;
    i=n;s=a;
    while (i>>=1)//每次移动递增
    {
        s*=s;
        if ((i&n)==i) s*=a;//解决奇偶
    }
    return s;
}

以上算法也可说是：快速幂取模算法的一个优化。
方法二，比较好理解点

unsigned long power(unsigned long m, unsigned long n) 
{ 
         unsigned long t = 1; 
         while(n > 0){ 
             if(n & 0x01UL == 1)  
                 t *= m; 
             m *= m; 
             n >>= 1; 
         }
         return t; 
}