/*---------------------------------------------------------------------------
File name: pow.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/22/2007 17:47:04
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Post: pow(a, b): can we do it iteratively using lgn multiplications?

Following code calculates a^b using lgn multiplications. But it is recursive.

Question:

Can we do it using a loop?

Don't use a stack to convert recursion into iteration, 'coz that does not solve
the problem.
*/

#include <stdio.h>

/**
Calculates a^b using lgn multiplications.
*/
int pow(int a, int n)
{
int t;

if(n==0)
return 1;

t=pow(a, n/2);
t*=t;
if(n&1)
t*=a;

return t;
}

int main()
{
int a=3, i;

for(i=0; i<21; ++i)
printf("%d\n", pow(a, i));

return 0;
}

对于a^b，可以将b视作若干2的幂的和的形式，例如2^10可以视作2^(2+8)=2^2*2^8，这样就表示成了若干 (a的(2的幂)的幂)的乘积 的形式，我用一个变量y循环得到a^2,a^4,a^8,...，用对b的位运算判断结果t是否应该有当前的y作为因子，如果有就乘上去

#include <stdio.h>
#include <stdlib.h>
int power(int a,int b)
{
    int t=1,y=a;
    while(b){
        if(b&1)
            t*=y;
        y=y*y;
        b>>=1;
    }
    return t;
}

int main()
{
    printf(\"%d\n\",power(2,10));
    printf(\"%d\n\",power(10,3));
    printf(\"%d\n\",power(1,100));
    printf(\"%d\n\",power(100,0));
    //system(\"pause\");
}

有收获!!!