用於計算循環緩衝區中剩餘空間的簡化算法？

Question

我想知道是否有一種更簡單（單一）的方式來計算循環緩衝區中的剩餘空間嗎？

int remaining = (end > start) 
       ? end-start 
       : bufferSize - start + end; 

Answer 1

如果你擔心不好預測條件句放慢你的CPU的管道，你可以這樣做：

int remaining = (end - start) + (-((int) (end <= start)) & bufferSize); 

但是，這可能是不成熟的優化（除非你真的確定這是一個熱點） 。堅持你目前的技術，這是更具可讀性。

Answer 2

失去條件：

int remaining = (end + bufferSize - start - 1) % bufferSize + 1 

編輯：-1和+1是的情況下end == start。在這種情況下，此方法將假定緩衝區爲空。根據緩衝區的具體實現情況，您可能需要對其進行調整以避免出現偏離1的情況。

Answer 3

根據C++標準，部分5.6，第4段：

二進制/操作員產生的商，和二進制％操作者產生了由第二所述第一表達的除法的餘數。如果/或％的第二個操作數爲零，則行爲未定義;否則（a/b）* b + a％b等於a。如果兩個操作數都是非負的，那麼餘數是非負的;如果不是，剩餘的符號是實現定義的。

一個腳註建議將商數四捨五入爲首選，這將使餘數爲負數。

因此，(end - start) % bufferSize方法不能可靠地工作。 C++沒有模塊化算術（除了無符號整型提供的意義）。

j_random_hacker推薦的方法是不同的，看起來不錯，但我不知道它是簡單或速度的任何實際改進。將布爾型轉換爲int型是很巧妙的，但需要進行心理分析，而且根據編譯器和機器的不同，可能會比使用？：更加昂貴。

我認爲你有最簡單最好的版本，我不會改變它。

Answer 4

嗯....

int remaining = (end - start + bufferSize) % bufferSize; 

13令牌，我贏了嗎？

Answer 5

如果您的循環緩衝區大小是2的冪，您可以通過讓start和end代表虛擬流中的位置而不是循環緩衝區的存儲區中的索引來做得更好。假設start和end是無符號的，以上變爲：

int remaining= bufferSize - (end - start); 

實際上得到元件移出緩衝區是有點複雜，但是開銷通常是足夠小的以2大小的循環緩衝區的功率（只是掩蔽與bufferSize - 1）使您的循環緩衝區的所有其他邏輯更簡單，更清潔。另外，你可以使用所有的元素，因爲你不再擔心end==start！

Answer 6

舊線程我知道，但認爲這可能會有所幫助。

不知道有多快實現了C++，但在RTL我們這樣做，如果大小是n^2

remaining = (end[n]^start[n]) 
      ? start[n-1:0] - end[n-1:0] 
      : end[n-1:0] - start[n-1:0]; 

或

remaining = if (end[n]^start[n]) { 
       start[n-1:0] - end[n-1:0] 
      } else { 
       end[n-1:0] - start[n-1:0] 
      };