时间戳

首页 > 解决方案 > 为什么在将中间结果分配给 int 之前将其转换为 long？

c++ - 为什么在将中间结果分配给 int 之前将其转换为 long？

问题描述

在 Codeforces 和 Codechef 的许多编码流和解决方案中，我看到当数字有点大并且我们需要将其分配给 int 时，我们将其转换为 long 而不是将其转换为 int

int maxAreaOfCake(int h, int w, vector<int>& hCuts, vector<int>& vCuts)
{
    hCuts.push_back(0);
    hCuts.push_back(h);

    vCuts.push_back(0);
    vCuts.push_back(w);

    int MOD = 100000007;

    sort(hCuts.begin(), hCuts.end());
    sort(vCuts.begin(), vCuts.end());

    int horizontal = 0;
    for(int i = 0; i < (int)hCuts.size() - 1; i++) horizontal = max(horizontal, hCuts[i+1] - hCuts[i]);
    

    int vertical = 0;
    for(int i = 0; i < (int)vCuts.size() - 1; i++) vertical = max(vertical, vCuts[i+1] - vCuts[i]);
    
    return (int) ((long)horizontal%MOD * (long)vertical%MOD)%MOD;
}

这是leetcode中MaxAreaOfCake问题的解决方案。在这里，由于返回类型是 int，我们最终将转换为 int，但在此之前，我们首先将其转换为 long。当我尝试将 long 更改为 int 时，出现运行时错误。如果有人知道答案，请分享:)

标签： c++castingmultiplicationinteger-overflow

解决方案

有问题的行是

return (int) ((long)horizontal%MOD * (long)vertical%MOD)%MOD;

强制转换为 long 确保表达式(long)horizontal%MOD * (long)vertical%MOD是两个long值的乘积。C 和 C++ 将算术运算的结果计算为其操作数的“最大”类型；如果你将两个ints 相乘，结果也是int如此。如果数学结果对于 int 而言太大，则会导致有符号溢出，这是未定义的行为。horizontal%MOD * vertical%MOD如果大于maximum ，就会发生这种情况int，例如因为操作数大于最大值的平方根int。为了防止代码将操作数转换为long，希望long' 的值范围更大（这可能是也可能不是真的）。如果它是真的，结果通常总是适合一个long（因为通常最大int小于最大long) 的平方根。然后使用乘法的结果来计算它的模MOD，它永远不会大于MOD-1并且因此小于最大值int。因此，将最终结果转换回 是安全的int，这是第一个(int) 所做的。但是大的中间结果，在最终模之前，必须在更大的值范围类型中计算。

考虑一下为了使这个逻辑健壮而必须执行的情况（如果 long并且int具有相同的值范围，则强制转换是徒劳的）我希望有一个std::numeric_limits<T>类似的模板bool would_overflow(T2 arg)，用于 T2 类型的每个 arg 返回该值是否可转换到 T 而不会溢出。

推荐阅读