c++ - 这种计算大数的方法是如何工作的？

Question

通常，要在 C++ 中处理超出 long long 范围的整数，您必须将它们表示为字符串并以这种方式对它们执行操作。但是，我在互联网上找到了这段代码，它似乎像魔术一样工作。它计算 2 的任意次幂之和(不包括 2^0)，即使它不能存储在 long long 中。

#include <iostream>  
#include <cmath>  
#include <iomanip>  
#include <sstream>  
using namespace std;

int main() {
    int n;
    stringstream ss;
    cin >> n;

    ss << fixed << setprecision(0) << pow(2, n + 1) - 2;

    if (n >= 54) {
        string a = ss.str();

        a[a.size() - 1] = ((a[a.size() - 1] - 48) - 2) + 48;

        cout << a;
        return 0;
    }

    cout << ss.str();

}

它是如何工作的？它适用于任何涉及大量的操作吗？如果 n 的值很大(我试过 1024)，它只会打印“inf”。这样计算出来的数字范围上限是多少？

下面的部分到底做了什么，为什么要这样做？

a[a.size() - 1] = ((a[a.size() - 1] - 48) - 2) + 48;

Answer 1

Will it work for any operation involving large numbers?

您可以使用 float 执行与使用整数相同的操作。但是每次计算都会出错，而且并不是所有的整数都是可表示的。

---

What's the upper-limit of the range of numbers that can be calculated this way?

取决于您的处理器使用的 double 浮点类型。

您可以使用 std::numeric_limits<double>::max() 找出最高可表示数.然而，这些高数字的精度非常差。并非所有整数都可以表示到这个数字。连续可表示整数的最大值是std::pow(std::numeric_limits<double>::radix, std::numeric_limits<double>::digits) .

---

What exactly does the following part do and why does it do it?

a[a.size() - 1] = ((a[a.size() - 1] - 48) - 2) + 48;

这可以简化为

a[a.size() - 1] -= 2;

它只是从最后一位(最低位)减去 2。它依赖于数学事实，即 2 的幂永远不会是 0 或 1 模 10(2⁰ 除外)，在这种情况下，最后一位数字将成为非数字字符。

它还依赖于 pow(2, n + 1) - 2 == pow(2, n + 1)对于 n >= 54 .该代码假定 float 遵循普遍存在的二进制 IEEE-754 格式，其中 std::pow(std::numeric_limits<double>::radix, std::numeric_limits<double>::digits)是std::pow(2, 54) .当n大于等于54，计算结果std::pow(2, 54 + 1)变得如此之大，以至于如果你从中减去一个小数字，如 2，最接近的可表示结果与你开始时的结果相同。计算的精度误差等于较小的操作数!该计算根本无法用 float 执行。这就是为什么后来用数字字符摆弄来修复它的原因。

所有 2 的幂(直到极限)都是可表示的，因此幂计算本身不会有任何精度错误。