4.快速计算乘方的算法
如计算2^13,则传统做法需要进行12次乘法。
[cpp]
/*计算n^p*/
unsigned power（unsigned n,unsigned p）
{
for（int i=0;i<p;i++） n*=n;
return n;
}
/*计算n^p*/
unsigned power（unsigned n,unsigned p）
{
for（int i=0;i<p;i++） n*=n;
return n;
}
该死的乘法，是时候优化一下了！把2*2的结果保存起来看看，是不是成了：
4*4*4*4*4*4*2
再把4*4的结果保存起来：16*16*16*2
一共5次运算，分别是2*2、4*4和16*16*16*2
这样分析，我们算法因该是只需要计算一半都不到的乘法了。
为了讲清这个算法，再举一个例子2^7:2*2*2*2*2*2*2
两两分开：（2*2）*（2*2）*（2*2）*2
如果用2*2来计算，那么指数就可以除以2了，不过剩了一个，稍后再单独乘上它。
再次两两分开，指数除以2: （（2*2）*（2*2））*（2*2）*2
实际上最后一个括号里的2 * 2是这回又剩下的，那么，稍后再单独乘上它 现在指数已经为1了，可以计算最终结果了：16*4*2=128
优化后的算法如下：
[cpp]
unsigned Power（unsigned n,unsigned p）
{
unsigned main=n; //用main保存结果
unsigned odd=1; //odd用来计算"剩下的"乘积
while （p>1）
{//一直计算，直到指数小于或等于1
if（（p%2）！=0）
{// 如果指数p是奇数，则说明计算后会剩一个多余的数，那么在这里把它
乘到结果中
odd*=main; //把"剩下的"乘起来
}
main*=main; //主体乘方
p/=2; //指数除以2
}
return main*odd; //最后把主体和"剩下的"乘起来作为结果
}
unsigned Power（unsigned n,unsigned p）
{
unsigned main=n; //用main保存结果
unsigned odd=1; //odd用来计算"剩下的"乘积
while （p>1）
{//一直计算，直到指数小于或等于1
if（（p%2）！=0）
{// 如果指数p是奇数，则说明计算后会剩一个多余的数，那么在这里把它
乘到结果中
odd*=main; //把"剩下的"乘起来
}
main*=main; //主体乘方
p/=2; //指数除以2
}
return main*odd; //最后把主体和"剩下的"乘起来作为结果
}
够完美了吗？不，还不够！看出来了吗？main是没有必要的，并且我们可以有更快的代码来判断奇数。要知道除法或取模运算的效率很低，所以我们可以利用偶数的一个性质来优化代码，那就是偶数的二进制表示法中的最低位一定为0!
完美版：
[cpp]
unsigned Power（unsigned n, unsigned p）
{ // 计算n的p次方
unsigned odd = 1; //oddk用来计算"剩下的"乘积
while （p > 1）
{ // 一直计算到指数小于或等于1
if （（ p & 1 ）！=0）
{ // 判断p是否奇数，偶数的最低位必为0
odd *= n; // 若odd为奇数，则把"剩下的"乘起来
}
n *= n; // 主体乘方
p /= 2; // 指数除以2
}
return n * odd; // 最后把主体和"剩下的"乘起来作为结果
}
unsigned Power（unsigned n, unsigned p）
{ // 计算n的p次方
unsigned odd = 1; //oddk用来计算"剩下的"乘积
while （p > 1）
{ // 一直计算到指数小于或等于1
if （（ p & 1 ）！=0）
{ // 判断p是否奇数，偶数的最低位必为0
odd *= n; // 若odd为奇数，则把"剩下的"乘起来
}
n *= n; // 主体乘方
p /= 2; // 指数除以2
}
return n * odd; // 最后把主体和"剩下的"乘起来作为结果
}
========================================================