爲4 * ceil（n/3）保證足夠的存儲空間，其中n是一個整數

假設n是一個整數（C中的一個int變量）。我需要足夠的空間來「四倍n除以3」的上限。我如何保證足夠的空間？爲4 * ceil（n/3）保證足夠的存儲空間，其中n是一個整數

您是否認爲malloc(4*(int)ceil(n/3.0))會這樣做，或者我必須添加（例如）1才能絕對安全（由於可能的舍入錯誤）？

2011-12-26 pf85

到KerrekSB的總體替代式這保證只有一個除法被使用，是計算

（N + M-1）/ M

要看到，它產生相同的，WR ite n = k*m + r與0 <= r < m。然後n%m == r，並且如果r == 0，我們有n+m-1 = k*m + (m-1)和(n+m-1)/m == k，否則n+m-1 = (k+1)*m + (r-1)和(n+m-1)/m == k+1。

最現代化的硬件爲您提供了一個寄存器，在另一個其餘(n%m)，當你做一個整數相除所得的商（n/m），所以你可以在一個部門得到Kerrek公式的兩個部分，和大多數編譯器將這樣做。如果編譯器沒有，但使用兩個分區，則計算速度將會相當慢，所以如果計算經常進行並且性能是一個問題，那麼可以用稍微不太明顯的代碼來解決編譯器的弱點。

在給定的情況下，malloc將

malloc(4*((n+2)/3));

但因爲它不是每一個人都很清楚公式做什麼，如果你使用它，解釋它在一個評論，如果你不需要要使用它，請使用更明顯的代碼。

來源

2011-12-27 00:10:31

+1對於很好的解釋和建議評論。 – 2011-12-27 13:33:47

要計算的n/m天花板整體，只是說：

n/m + (n % m == 0 ? 0 : 1)

總而言之，說malloc(4 * (n/3 + (n % 3 ? 1 : 0)));。

來源

2011-12-26 23:32:40

或者'（n + m-1）/ m'只在編譯器不夠聰明時使用一個除法。 – 2011-12-26 23:35:09

@DanielFischer你是什麼意思？你能詳細說明嗎？你到底會把什麼放到malloc中？ – pf85 2011-12-26 23:39:01

@DanielFischer：非常好！爲什麼不把它作爲答案:-) – 2011-12-26 23:51:40

雖然Kerrek SB有一個確切的答案，實際上大多數工程師會使用malloc (4 + 4 * n/3)或（等效）malloc (4 * (1 + n/3))。 C的規則將n/3評估爲導致將餘數截斷的整數。給表達式增加一點可以確保分配忽略的任何分數都被分配。

最多可能會浪費三個字節。只有在數以千計的情況下，任何額外的計算才能解釋爲—。實現malloc通常將存儲分配整理爲4,8或16字節的倍數，以簡化其內務處理。

考慮3字節內存的成本：Current pricing是每GB 5美元到15美元。三個字節花費$ 0.000 000 009

來源

2011-12-26 23:40:47 wallyk

鑑於Bort和Daniel的解決方案實際上在所有情況下都會在相同數量的操作中產生正確的鼻子數量，我會說這些都是可取的......記憶不僅僅是關於金錢，但也關於緩存局部性和類似的東西。 – 2011-12-26 23:54:58

可以實現純整數運算同樣的事情這就保證了您分配正確的內存量：編輯固定支架

malloc(4*((n+2)/3))

來源

2011-12-26 23:41:57 Bort

不應該有一組額外的括號嗎？ – 2011-12-26 23:53:08

ups是啊我只是在思考它的時候看着ceil（n/3）部分。修復。 – Bort 2011-12-26 23:56:01

爲4 * ceil（n/3）保證足夠的存儲空間，其中n是一個整數

回答

相關問題