幂函数O(logN)实现

幂函数O(logN)实现

假设一个整数是X，如何最快的求解X的Y次方。(以下X=10,Y=75为例)

1.75的二进制为1001011

2.10^75=10^64 * 10^8 * 10^2 * 10^1 (先计算10的1次方，再根据10的1次方计算10的平方，再根据10的2次方计算10的四次方，……，再根据10的32次方计算出10的64次方。即75的二进制有多少位我们就用了多少次乘法)。

3.把步骤2中应该乘的项累乘起来即可。(64、8、2、1，对应75二进制中的1，应该累乘。32、16、4，对应75二进制中的0，不用累乘)。

//C语言实现
#include<stdio.h>
int main()
{
    int X,Y,power=1;
    printf("计算X的Y次幂\n");
    scanf("%d,%d",&X,&Y);
    for(;Y!=0;X=X*X,Y=Y>>1)
    {
        if((Y&1)!=0)//Y&1!=0代表Y的二进制中为的1的时候
        power=power*X;
    }
    printf("计算结果为：%d",power);
    return 0;
}