程序代码：

#include <stdio.h>

#define MAX 10001
int ss[MAX][MAX/3] = {{1, 1}, {1, 2}, {1, 4}};

void Multiply(int a)
{
    if (ss[a+a][0])    return;

    int temp, n, i, j;
    n = ss[a][0] * 2 + 1;

    for (i = ss[a][0]; i > 0; --i)
    for (j = ss[a][0]; j > 0; --j)
        ss[a+a][n-i-j] += ss[a][i] * ss[a][j];

    for (i = 1; i < n-2; ++i)
    {
        ss[a+a][i+1] += ss[a+a][i] / 10;
        ss[a+a][i] %= 10;
    }
    while (ss[a+a][i] > 9)
    {
        ss[a+a][i+1] += ss[a+a][i] / 10;
        ss[a+a][i++] %= 10;
    }
    ss[a+a][0] = (i -= !ss[a+a][i]);

    for (j = 1;j <= i;++j, --i)
        temp = ss[a+a][j], ss[a+a][j] =
        ss[a+a][i], ss[a+a][i] = temp;
}

void Mul(int n)
{
    if (ss[n][0])    return;

    int len = ss[n-1][0];
    int i, j, temp = 0;

    for (i = 1;len > 0;--len)
    {
        temp += ss[n-1][len] * 2;
        ss[n][i++] = temp % 10;
        temp /= 10;
    }
    if (temp) ss[n][i] = temp;
    else    --i;

    ss[n][0] = i;
    for (j = 1;j < i;++j, --i)
        temp = ss[n][j], ss[n][j] =
        ss[n][i], ss[n][i] = temp;
}

void Get(int n)
{
    if (ss[n][0])    return;

    Get(n / 2);Multiply(n / 2);
    if (n & 1)    Mul(n);
}

int main()
{
    int i, n;
    while (scanf("%d", &n) != EOF && n < MAX && n >= 0)
    {
        Get(n);printf("2 ^ %d = ", n);
        for (i = 1;i <= ss[n][0];printf("%d", ss[n][i++]));
        puts("");
    }
    return 0;
}