B2034 计算 2 的幂

Starw · 2021-07-03 21:49:01 · 题解

这里介绍一下做本题的三种方法（一种比一种快）。

1.常规做法：

时间复杂度 O(n)。

代码：

#include<bits/stdc++.h>//万能头
using namespace std;
int pow_2(int x){
    int ans=2;
   if(x==0) return 1;//这里需要特判一下2^0
    for(int i=2;i<=x;i++)
        ans*=2;
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    printf("%d",pow_2(n));
    return 0;//好习惯*1
}

2.快速幂：

这里就不赘述了，详情请见P1226 【模板】快速幂||取余运算。

时间复杂度 O(logn)。

代码：

#include<bits/stdc++.h>//万能头
using namespace std;
int quick_pow(int n,int p){//快速幂
    int ans=1;
    while(p>0){
        if(p&1) ans=ans*n;
        p/=2,n*=n;
    }
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    printf("%d",quick_pow(2,n));
    return 0;//好习惯*2
}

3.位运算：

这里要用到左移运算符 <<,这个东西的意思是把在它右边的数在二进制的情况下往左边移动它左边的数位，并自动用 0 补齐，由于是二进制，所以 a<<b 就相当于 a*2^b。

时间复杂度 O(1)。

代码：

#include<bits/stdc++.h>//万能头 
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    printf("%d",1<<n);//位运算
    return 0;//好习惯*3
}