2的n次幂快速求法

2的n次方怎么求？

方法1：暴力法：

#include
using namespace std;

int n;

int main()
{	
	cin>>n;
	int ans=1;
	for(int i=1;i<=n;i++)  //乘n次
		ans*=2;
	cout<<ans;
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法2：快速幂求法：

比如求2的7次方，7转换为二进制就是111
2⁷=2¹⁰⁰*2⁰¹⁰*2⁰⁰¹

从7的最低位开始，如果当前位为1，那么乘上当前位对应的二进制转10进制值。

再一个，如果不用高精度，那么对答案取模

(a*b)%mod=((a%mod) *(b%mod))%mod

#include
using namespace std;

const int mod =100007;


int main()
{
	int n;
	cin >> n;
	int sum = 0;
	int k = 5;
	int ans = 1;
	for (int i = 1; n; i++)
	{
		if (n & 1)  //n最低位是1
			ans = ((ans%mod) * (k%mod))%mod;
		n=n >> 1;
		sum++;
		k=((k%mod)*(k%mod))%mod;  //k=k*k.k表示下一位二进制对应的十进制数
	}
	cout << ans << endl;
	cout << "运行了" << sum << "次！";
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26