algorithm - 寻找存储大整数的最有效基的算法

Question

非常大的整数通常作为可变长度的数字数组存储在内存中，这与 Java 或 C 中大多数原始“int”或“long”类型的直接二进制表示相反。考虑到这一点，我很想知道可以计算的算法：

1. 整数必须达到多少计数才能将其存储为 BigInteger（或等效的任意精度算术构造）并具有给定的整数位基数；

2. 哪个基数最有效地存储这个大整数的数字。

我提到了“效率”；这样，我的意思是我主要关心 BigInteger 将消耗的空间量，尽管我也有兴趣听到有关处理速度或时间复杂度的任何评论。

Answer 1

如果以原始二进制格式存储，整数应该占用最少的空间（除非它可能是一个小整数并且数据类型对它来说太宽 - 以 128 位存储 1 long long）。以不同方式存储不会节省任何内存，并且用于使使用此类整数的工作更容易。

如果逐个字节，这将转换为 256'ecimal radix - 256 个可能的值，尽可能多的字节可以容纳。

Answer 2

1. BigInt 永远不会比硬件直接支持的整数类型之一更有效。如果您可以直接使用受支持的内容，请使用它。
2. 硬件最有效地支持什么，可能是 2 的幂，或者通常等效地是二进制。