c# - 在不使用 BigInt 的情况下计算 2^1000 的总和

Question

你们中的一些人可能会注意到这个问题是 problem 16来自 Project Euler .我已经使用 C# 4.0 的新“bigInt”功能解决了这个问题，它相当简单，但也没有真正学习我应该学习的一切。我假设因为它是 2 ^ 1000，所以会有某种移位解决方案，但我无法弄清楚它究竟是如何工作的。

有人知道不用 bigint 就能计算 2^1000 的方法吗？

Answer 1

这道题最难的不是计算(从 1 开始，乘以 1000 次)，而是以十进制显示答案。考虑到这一点，您可能会发现以某种 BCD 表示形式(例如以 1000 为基数)执行计算在概念上更容易。然后执行 2 的长乘法一千次。这是一个 Python 解决方案:

def mul2(n):
    result = []
    carry = 0
    for i in n:
        i = i * 2 + carry
        carry = 0 if i < 1000 else 1
        result.append(i % 1000)
    if carry: result.append(1)
    return result

n = [1]
for _ in range(1000):
    n = mul2(n)

print ''.join('{0:03}'.format(i) for i in reversed(n)).lstrip('0')