c++ - 整数溢出问题

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 

很明显，存在溢出问题。现在要解决这个问题，我将行 result.push_back(result[i-1] * (rowIndex+1-i)/i); 修改为 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)

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

---

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

vector<long>

甚至

vector<unsigned long>

或者，感谢 @WorldSEnder，

vector<unsigned long long>

不过，请注意该标准并不保证 long 或 long long 比 int 长。它也不保证 int 在 [-2147483648, 2147483647] 范围内。