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

次方（快速幂取模）"/>

【算法】求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; 
}