如何计算大n的2 ^ n？

Question

我正在尝试编写一个程序，该程序接受一个数字n作为输入，并将2的结果输出为的幂n。问题是，n可能会很大（最多100,000个）。本质上，我正在尝试计算pow(2, n);非常大的数字。

我认为这样做的方法是将数字存储在数组中，因为没有内置的数值类型可以容纳如此大的值。

这些数字采用十进制格式（以10为基数）。

我使用的是C，而不是C ++，因此无法使用STL向量和其他C ++容器。我也不能使用外部库，例如GMP。我需要在纯C语言中手动实现该算法。

Answer 1

问题不是计算 2 的高次幂，而是将这个数字转换为十进制表示：

• 让我们用无符号 32 位整数数组表示大数。
• 计算 2 ⁿ就像设置一个位一样简单。
• 可以通过将该数字重复除以 1000000000 来转换为二进制，每次产生 9 位数字。

这是一个简单但快速的实现：

#include <stdint.h>
#include <stdio.h>

void print_2_pow_n(int n) {
    int i, j, blen = n / 32 + 1, dlen = n / 29 + 1;
    uint32_t bin[blen], dec[dlen];
    uint64_t num;

    for (i = 0; i < blen; i++)
        bin[i] = 0;
    bin[n / 32] = (uint32_t)1 << (n % 32);

    for (j = 0; blen > 0; ) {
        for (num = 0, i = blen; i-- > 0;) {
            num = (num << 32) | bin[i];
            bin[i] = num / 1000000000;
            num = num % 1000000000;
        }
        dec[j++] = (uint32_t)num;
        while (blen > 0 && bin[blen - 1] == 0)
            blen--;
    }
    printf("2^%d = %u", n, dec[--j]);
    while (j-- > 0)
        printf("%09u", dec[j]);
    printf("\n");
}

int main() {
    int i;
    for (i = 0; i <= 100; i += 5)
        print_2_pow_n(i);
    print_2_pow_n(1000);
    print_2_pow_n(10000);
    print_2_pow_n(100000);
    return 0;
}

输出：

2^0 = 1
2^5 = 32
2^10 = 1024
2^15 = 32768
2^20 = 1048576
2^25 = 33554432
2^30 = 1073741824
2^35 = 34359738368
2^40 = 1099511627776
2^45 = 35184372088832
2^50 = 1125899906842624
2^55 = 36028797018963968
2^60 = 1152921504606846976
2^65 = 36893488147419103232
2^70 = 1180591620717411303424
2^75 = 37778931862957161709568
2^80 = 1208925819614629174706176
2^85 = 38685626227668133590597632
2^90 = 1237940039285380274899124224
2^95 = 39614081257132168796771975168
2^100 = 1267650600228229401496703205376
2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
2^10000 = 1995063116880758384883742<...>91511681774304792596709376
2^100000 = 9990020930143845079440327<...>97025155304734389883109376

2 ¹⁰⁰⁰⁰⁰有 30103 个数字，正好是floor(100000 * log10(2)). 它在我的旧笔记本电脑上执行时间为 33 毫秒。