我怎样才能知道存储 1 到 2^100 之间的每个数字需要多少存储空间？

Question

在代码中处理大量数字时，我完全是初学者，我知道这绝对是错误的方法，但这就是我的开始。

import tqdm

try:
    total = 0
    for num in tqdm.tqdm(range(2**100), total=2**100):
        total += len(bin(num)) - 2
finally:
    with open('results.txt', 'w') as file:
        file.write(f'{total=}')

我得到的结果是：

0%|                  | 87580807/1267650600228229401496703205376 [00:39<159887459362604133471:34:24, 2202331.37it/s]

显然这种方法会花费 太长的时间。我知道我可以尝试制作多核，但我认为这不会对速度产生太大影响。

我有哪些选择？

使用其他语言（如 C）是否会显着提高速度，以至于需要数天或数小时而不是数亿年？我可以使用另一个 approach/algorithm 吗？

Answer 1

好的，我明白了。我用了 .

所以代码如下：

total = 0
for power in range(1, 101):
    total += ((int('1' * power, base=2) - int('1' + '0' * (power - 1), base=2)) + 1) * power

total 等于 125497409422594710748173617332225，表示存储 1 到 2^100 之间的每个数字所需的字节数。

在某些情况下，地球总存储容量的 ≈425414947195.2363 倍才能存储 1 到 2^100 之间的所有数字。

参考：https://www.zdnet.com/article/what-is-the-worlds-data-storage-capacity/

Answer 2

有趣的问题，但不是所有的问题都应该用蛮力解决，算法部分来了。查看您的问题，您似乎想要计算 os 位所需的位数 n。现在如果我们看 closely,

number of bits    total number of numbers we can represent
1                  2**1 = 2
2                  2**2 = 4
3                  2**3 = 8
4                  2**4 = 16
5                  2**5 = 32
...

所以总和就像

1*2 + 2*2 + 3*2^2 + 4*2^3 + ...
= 1 + 1*2^0 + 2*2^1 + 3*2^2 + 4*2^3 + ...
= 1 + sum(k*2^(k-1)) with n from 1 to number of bits
= 1 + (k*2^k - 2^k +1)
= k*2^k - 2^k + 2

可见呈几何级数。使用上面的总和可以确定公式

import math

def log2(x):
    return math.log(x) / math.log(2)

def count_the_total_number_of_bits_till(n):
    neares_2_to_the_power = math.floor(log2(n))
    actual_number_of_bits_required = math.ceil(log2(n))
    
    sum_1 = ((neares_2_to_the_power * (2**neares_2_to_the_power)) - (2**neares_2_to_the_power) + 2)
    extra_sum = ((n - 2**neares_2_to_the_power) * (actual_number_of_bits_required))
    
    return sum_1 + extra_sum

count_the_total_number_of_bits_till(2**10)

你在做什么

sum_ = 0
for i in range(2**10): 
#equivalent to 
# count_the_total_number_of_bits_till(2**10)
    sum_ += len(bin(i)[2:])

print(sum_)

我怎样才能知道存储 1 到 2^100 之间的每个数字需要多少存储空间？

How can I find out how much storage it would take to store every number between 1 and 2^100?

python

large-data

largenumber