您当前的位置: 求2的N次方有没有什么高效率运算啊， N在10000左右。
以下是我的解法。。没有什么可靠依据
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10000
int main(int argc, char *argv[]) {
int n;
scanf("%d",&n);
char result[N];
int i;
for(i=0;i<N;i++){
result[i]=0;
}
result[N-1] = 2;
char offset = 0;
int j;
for(i=1;i<n;i++)
{
int flag = 0;
j = N-1;
while (1) {
if(result[j]+offset==0){
if(++flag==5) //我查了2的乘方表，发现连续有五个0，就意味着没有更多的位数了。这是我的想法。
break;
}
else flag = 0;
result[j] = 2*result[j] + offset;
if(result[j]>=10)
{
offset = 1;
result[j] = result[j] - 10;
j--;
continue;
}
offset = 0;
j--;
}
}
// for (j=j;j<N;j++ )
// {
// printf("%c",result[j]+'0');
// }
// printf("\n");
int sum=0;
for(i=j;i<N;i++)
{
sum = sum + result[i];
}
printf("%d",sum);
}
幂运算
效率
算法
c
------解决方案--------------------
本题的特殊性：
x*2=x+x。用加法来替代乘法
或 x*2 = x << 1。用位移来替代乘法
然后，剩下的就是大数加法了。一般做法是用数组来存每一位
建议不要用Flag连续5个0来表示没有更高位，毕竟这不严谨。
可以记录每次加完后的最高位（本题的特殊性：最多比前一次多一位）
------解决方案--------------------
还可以进一步提高效率：
由于9*16=144 < 256，所以可以一次计算 *16（2^4)，当算后指数还没完，再用 ^2
比如（这里n小些，能说明问题就成）：
2^11 = (2^4) * (2^4) * (2^2) * (2^1)
------解决方案--------------------
必然要用大数乘法，2^16=65536，类似这样反复乘就可以了，直到剩余部分小于2^16,然后查表直接乘剩余部分
------解决方案--------------------
1楼说的对，如果是2的N次幂求值，就是将直接1左移N位。
但是受计算机数据类型的限制，在windows平台下的32位操作系统机器上最大整数位long long,也就是64位。64位操作系统的机器，最大位数是128位。也就是说在指数小于等于128的时候可以直接使用这种简单的移位运算。
《数据结构与算法分析》mark.Allen.weiss中提供的分治算法可以用于解决任意情形的指数运算（或者称为幂运算），是一个典型算法。
bool isEven(int n)
{
return n%2 == 0;
}
long pow(long x, int n)
{
if (n == 0)
return 1;
if (n == 1)
return x;
if(isEven(n))
return pow(x*x, n/2);
else
return pow(x*x, n/2)*x;
}
------解决方案--------------------
1楼和4楼已经解决，等待结贴接分
------解决方案--------------------
很高啊，我是来学习的！！！
------解决方案--------------------