一个用浮点数计算2的幂的技巧

来自WC的小技巧,Pascal不支持

适用范围

仅适用于计算2n2^n的精确值,且n<214\left\vert n\right\vert<2^{14}

浮点数能精确表示2n2^n,因为大部分浮点数内部都以2为底数,n的范围与浮点数类型有关。常用浮点数最高精度的long double也只有15位阶码。

使用方法

直接使用pow函数即可计算。

C++

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
cout.precision(n>0?0:-n);
cout<<fixed<<pow(2.0L,n)<<endl;
return 0;
}

C

1
2
3
4
5
6
7
8
9
#include<stdio.h>
#include<math.h>
int main(void)
{
int n;
scanf("%d",&n);
printf("%.*Lf\n",n>0?0:-n,powl(2.0L,n));
return 0;
}

浮点数常量的L后缀表示long double

Windows下scanf/printf

Windows下通常使用MinGW,部分版本可能无法正常使用%lld%Lf

解决方法非常简单,在程序首部加入:

1
#define __USE_MINGW_ANSI_STDIO 1

例题

洛谷P1760:求有n个圆盘的汉诺塔的最少移动步数(n15000n\le15000)。

根据常识,答案等于2n12^n-1

由于n的范围刚好可以使用上述技巧,而且-1也很方便,直接在最低位-1即可,显然不会退位。

程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
stringstream ss;
ss.precision(0);
ss<<fixed<<pow(2.0L,n);
string s=ss.str();
s[s.length()-1]--;
cout<<s<<endl;
return 0;
}

这里利用了字符串流,当然用sprintf也完全没有问题。实测比手写高精度快很多,代码也很简单。