1到40亿求和需要多少存储空间

Question

受到这个问题的启发（找到一个不在四十亿给定整数之中的整数）。

存储一个 1 到 40 亿数字之和的整数需要多少存储空间？

例如，1+2+3+4+5 = 15。1 到 100 万的总和 = 500,000,500,000。

这里是一个可能有帮助的算法

Answer 1

您链接的函数描述如何查找第 n 个Triangle Number ，定义为从 1 到 n 的 n 个自然数之和。

将 40 亿作为 n 代入函数，得到 8000000002000000000。

将其表示为位数，可以通过取该值的以 2 为底的对数并向上舍入来计算出 -

ceil(log(8000000002000000000)/log(2)) = 63

因此，需要 63 位存储空间。

Answer 2

In [12]: import math

In [13]: n=4000000000

In [15]: sumn = n*(n+1)/2

In [16]: sumn
Out[16]: 8000000002000000000L

In [24]: math.log(sumn)/math.log(2)
Out[24]: 62.794705708333197

答案：63 位。

Answer 3

如果您为整数选择适当的编码，一位就足够了。

如果您可能需要存储超过 2^n 个可能的值，则只需要超过 n 位。这里您只需要能够存储一个值。