整数溢出问题

Question

vector<int> getRow(int rowIndex) {
vector<int> result;
if(rowIndex < 0)   return result;
if(rowIndex == 0){
    result.push_back(1);
    return result;
}
for(int i = 0; i < rowIndex+1; i++){
    if(i == 0)  result.push_back(1);
    else{
        result.push_back(result[i-1] * (rowIndex+1-i)/i);
    }
}
return result;
}
int main()
{
    vector<int> tmp = getRow(30);
    for(int i = 0; i < tmp.size(); i++){
        cout << tmp[i] << " ";   
    }
    cout << endl;
    return 0;
}

这是LeetCode中的Pascal三角形编码问题，它要求输出Pascal三角形的第n行。使用rowIndex=30，输出如下所示：

1 30 435 4060 27405 142506 593775 2035800 5852925 14307150 30045015 54627300 86493225 119759850 145422675 -131213633 -123012780 -101304642 -73164463 -46209134 -25415023 -12102391 -4950978 -1722079 -502273 -120545 -23181 -3434 -367 -25 0 

显然存在溢出问题。现在为了解决这个问题，我修改了行< code > result . push _ back(result[I-1]*(rowIndex 1-I)/I)；到< code > result . push _ back((double)result[I-1]*(double)(rowIndex 1-I)/I)；。它产生正确的输出:

1 30 435 4060 27405 142506 593775 2035800 5852925 14307150 30045015 54627300 86493225 119759850 145422675 155117520 145422675 119759850 86493225 54627300 30045015 14307150 5852925 2035800 593775 142506 27405 4060 435 30 1 

有人可以解释一下这里的问题到底是什么吗？我们知道有符号整数值的范围是 -2147483648 到 2147483647。如果不进行铸造，为什么在值155117520打印为溢出-131213633？

Answer 1

一.表达方式

result[i-1] * (rowIndex+1-i)/i

乘法首先发生，并导致溢出:

result[i-1] * (rowIndex + 1-i)

然后结果除以< code>i，产生负输出。

顺便说一句，如果您决定强制转换，请避免强制转换为Double，因为可能存在舍入问题。您可以尝试long，但一开始使用可能更好。

vector<long>

或者甚至

vector<unsigned long>

或者，多亏了@WorldSEnder，

vector<unsigned long long>

尽管如此，请注意，该标准并不能保证long或long long长于int。它也不能保证int在[-2147483648,2147483647]范围内。