像unsigned int溢出一樣表現。是什麼造成的？

我有這個功能，它可以生成所謂的「三角形數字」的指定數量。如果我打印出後綴，則數字會增加，跳下來，然後再次增加。當我上升時，三角形數字永遠不會變低，所以一定會發生某種溢出。我試圖通過添加行if(toPush > INT_MAX) return i - 1;來嘗試修復它，以便在結果溢出時嘗試停止生成更多數字的函數（並返回它生成的數字）。然而，這不起作用，輸出繼續不正確（增加一段時間，跳到一個更低的數字，然後再次增加）。我添加的這條線實際上並沒有做任何事情。沒有達到收益。有人知道這裏發生了什麼嗎？像unsigned int溢出一樣表現。是什麼造成的？

#include <iostream> 
#include <deque> 
#include <climits> 
int generateTriangleNumbers(std::deque<unsigned int> &triangleNumbers, unsigned int generateCount) { 
    for(unsigned int i = 1; i <= generateCount; i++) { 
     unsigned int toPush = (i * (i + 1))/2; 
     if(toPush > INT_MAX) return i - 1; 
     triangleNumbers.push_back(toPush); 
    } 
return generateCount; 
}

來源

2013-03-08 Memento Mori

我無法工作的第一個價值是什麼？如果您手動進行特定計算，您觀察到了什麼？ – 2013-03-08 09:47:06

您如何期待任何數字嚴格大於最大數目？ – Mat 2013-03-08 09:47:47

你應該檢查你的計算的各個步驟。具體來說，如果溢出發生在'（i *（i + 1））'中，那麼之後就不能檢測到它。 – 2013-03-08 09:49:27

第92682個三角形數字已經大於UINT32_MAX。但是這裏的罪魁禍首早於計算i * (i + 1)。在那裏，計算溢出了第65536個三角形數字。如果我們問Python以其原生bignum支持：

>>> 2**16 * (2**16+1) > 0xffffffff 
True

糟糕。然後，如果你檢查你存儲的數字，你會看到你的序列回落到低值。爲了試圖效仿的標準說，關於這種情況下的行爲，在Python：

>>> (int(2**16 * (2**16+1)) % 0xffffffff) >> 1 
32768

，這是你的第六萬五千五百三十六三角形數量，這是不正確看到價值。

這裏檢測溢出的一種方法是確保您生成的數字序列是單調的;也就是說，如果生成的第N個三角形數嚴格大於第（N-1）個三角形數。

爲了避免溢出，你可以使用64位變量來都產生&存儲它們，或者如果你需要大量的三角形數字使用一個大數字圖書館。

來源

2013-03-08 09:58:22

發生的事情的價值。我沒有想到簡單地檢查新數字是否大於最後一個數字。我改變了代碼，現在它在正確的時間退出。 – 2013-03-08 10:05:59

在Visual C++ int（當然unsigned int的）是即使在64位計算機的32位。

使用unsigned long long或uint64_t來使用64位值。

來源

2013-03-08 09:47:23

INT_MAX是signed int的最大值。這大約是unsigned int（UINT_MAX）的最大值的一半。您計算的toPush可能會遠遠高於UINT_MAX，因爲您將該值平方（如果它接近INT_MAX，結果將比您的toPush可容納的UINT_MAX大得多）。在這種情況下，toPush將環繞併產生比前一個更小的值。

首先，您與INT_MAX的比較存在缺陷，因爲您的類型爲unsigned int，而不是signed int。其次，即使與UINT_MAX比較也是不正確的，因爲它意味着toPush（比較表達式的左操作數）可以保持一個高於最大值的值 - 這是不可能的。正確的方法是將您生成的數字與前一個數字進行比較。如果它更低，你知道你有溢出，你應該停下來。

另外，您可能希望使用可以容納更大範圍值的類型（例如unsigned long long）。

來源

2013-03-08 09:59:03 SomeWittyUsername

像unsigned int溢出一樣表現。是什麼造成的？

回答

相關問題