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

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

适用范围

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

浮点数能精确表示$2^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个圆盘的汉诺塔的最少移动步数($n\le15000$)。

根据常识，答案等于$2^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也完全没有问题。实测比手写高精度快很多，代码也很简单。