首页 > 代码库 > 快速求幂运算笔记

快速求幂运算笔记

2024-07-07 12:33:16   227人阅读

如何快速求x得n次方呢？

首先C++里面有个pow如何实现呢？自己查查，里面使用double，肯定更麻烦，还有jianzhi

我们会顺手写下

int res=1;

for(int i=1;i<=n;i++)

{

res*=x;

}

学习一下快速幂，logn内计算出来，使用N的二进制，只需要logN就可以计算。

正要的就是计算每个为1对应的基数。列入： 11是多少？是二进制的话，就是1*2^1+1

那么x^(11)呢，两个1对应的基数是多少呢？低位1对应的是X,高位1对应的是X^2,因此，就是位于第一位基数为x，第二位基数为X^2,第三位是X^4,X^8 ,从中我们看出前一位的基数的平方是后一位的基数。

因此对于 11011 就是对于0位，就是1，对于1为……

 

#include<iostream>
using namespace std;
int pow1(int x,int n)
{
    int res=1;
    for(int i=1;i<=n;i++)
    {
        res*=x;
    }

    return res;

}
int pow2(int x,int n)
{
    int base=x;
    int res=1;
    while(n)
    {
        if(n&1) res*=base;
        base=base*base;//每一位的基数的增长。

        n=n>>1;
    
    
    }

    return res;

}
//顺便写一个

int main()
{
    int x, n;
    cin>>x>>n;
    while(x)
    {
    cout<<pow1(x,n)<<endl;
    cout<<pow2(x,n)<<endl;
    cout<<pow(x,n)<<endl;
    cin>>x>>n;
    
    }



}


联系
我们