如何測試n/2 * 3 + n％2 * 2是否會溢出？

我該如何重寫這個測試，以便測試本身不會溢出？我可以使用(size_t) -1爲單數（2的冪減1）的事實嗎？如何測試n/2 * 3 + n％2 * 2是否會溢出？

size_t size; 
... 
if ((size * 3U + 1U)/2U > (size_t) -1) { 
    /* out of address space */ 
}

編輯：對不起，我的問題的標題是錯誤的。我不想檢查(n * 3 + 1)/2是否會溢出，但是如果n/2 * 3 + n % 2 * 2會。我改變了標題。感謝您對錯誤問題的正確答覆。

來源

2013-10-26 potrzebie

'size'的類型是什麼？ – pburka

你可以使用比'size'類型更大的類型嗎？ – zch

如果'（n * 3 + 1）/ 2'溢出，那麼'n * 3 + 1'也會溢出。所以你可以檢查'n>（SIZE_MAX - 1）/ 3'。 – 2013-10-26 21:24:19

下面是這個精確公式的解決方案，其背後的推理不適用於一般情況，但對於給定的和其他許多情況，它的確如此。

當size*3 + 1無法表示時，溢出發生，無符號整數除法永遠不會溢出。所以，你的情況應該是size*3 + 1 > max_value。這裏，max_value是所有位設置的無符號值，用(size_t)-1生成。

+1可以簡單地移動到右側而不會調用溢出，因爲max_value肯定大於1，所以我們到達size*3 > max_value - 1。同樣，可以移動*3而不引發溢出。所以你需要檢查的是size > (max_value - 1)/3。

請注意，相反的是我原來說（過失），size > max_value/3不起作用，因爲MAX_VALUE 是 3的倍數時，整數類型爲無符號（條件是，有一個連可用於正數的位數）。所以，當大小爲0x5555時，我們得到3*size = 0xffff和3*size + 1 = 0x0000。對不起，混合起來。

來源

2013-10-26 22:05:29 cmaster

_Signed_整數除法_can_溢出（例如'INT_MIN/-1'），但在這裏顯然無關緊要。 –

另外，爲什麼'max_value'不能是3的倍數？實際上，由於'size_t'必須包含偶數位，所以'max_value' _必須是3的倍數。 –

@JoshuaGreen Nitpick：'size_t'不需要偶數位，但除此之外我同意你的看法。 – pburka

如何測試n/2 * 3 + n％2 * 2是否會溢出？

回答

相關問題