Целочисленные проблемы с переполнением

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, которая запрашивает вывод 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

I выражение

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].