任何簡明的方式來計算出n *（N + 1）/ 2和處理溢出同時

我試圖實現n * (n + 1)/2知道n爲int < = 2^16 - 1（這保證n * (n + 1)/2 <= 2^31 - 1所以有沒有溢出）。我們知道n * (n + 1)/2保證是非負整數。當在程序中計算這個值時，如果我們先乘以n *(n + 1)，我們可能會遇到整數溢出問題。我的想法是使用笨拙的條件：任何簡明的方式來計算出n *（N + 1）/ 2和處理溢出同時

int m; 
if (n % 2 == 0) { 
    m = (n/2) * (n + 1); 
} else { 
    m = n * ((n + 1)/2); 
}

有沒有更簡潔的方式來做到這一點？

來源

2017-09-17 Ling Gu

'長TMP = N *（N + 1）; m = tmp/2; '？ –

@MichelBillaud'long'在某些系統上可能仍然是32位（例如Microsoft Visual C++編譯器，即使在64位系統上）。 –

那麼，@某些程序員夥計，'long long tmp'，https://msdn.microsoft.com/en-us/en-en/library/s3f49ktz.aspx –

你怎麼看待：

m = ((n + (n & 1)) >> 1) * (n + !(n & 1));

說明：

這個解決方案努力實現兩個目標：

不會溢出
避免使用if then else狀態，管道友好

爲了避免溢出，我們首先分割和乘法。一旦劃分完成一半的數量（2）它有一個有趣的屬性：如果次數是奇數的劃分是準確的，並且可以通過一個簡單的權篩選由1

可以這樣做，以保證沒有if then else條件，我們使用下面的技巧：

如果數字是奇數，這意味着它的低位是零（用1捕獲它），否則它是偶數。因此，如果數字是奇數，我們除以2，否則，我們首先加1，以確保它是奇數和除法。

換句話說，這種解決方案等效於：

if (n is odd) 
    m = (n >> 1) * (n + 1); 
else 
    m = ((n + 1) >> 1) * n;

來源

2017-09-17 16:53:59 Amadeus

我認爲這是行不通的。 –

它不起作用，因爲'n + n＆1'被評估爲'（n + n）＆1'，總是'0'。試圖計算'm =（（n +（n＆1））>> 1）*（n +〜（n & 1));'沒有筆和紙給我頭痛 – chqrlie

恐怕還有另一個問題：'' （n +〜（n＆1））'應該是'（n +！（n＆1））'，這更可讀爲'（n + 1 - （n＆1））'。 – chqrlie

的最簡單的解決方案是可能使用更大的中間類型：

int m = (int)((long long)n * (n + 1)/2) ;

這是沒有必要鑄所有操作數，因爲自動類型促銷將適用。

來源

2017-09-17 16:57:21 Clifford

這個問題更普遍 - 如果計算的類型本身很長，應該使用什麼。「長長的」？：D –

@ PeterJ_01：在這種情況下，問題非常具體：_「知道n是一個'int' <= 2^16 - 1」_。在這個具體案例中，「一般」解決方案會不必要地複雜。 – Clifford

@ PeterJ_01：其他人（包括您）已經提出了一般解決方案。然而，chqrlie包含了明確的解釋，並在他的答案中將解決方案與其他人進行了比較，在我看來，這樣更好。我不需要重複。 – Clifford

有使用三元運算符來編寫測試更簡潔的方式：

int m = (n % 2 == 0) ? (n/2) * (n + 1) : n * ((n + 1)/2);

但它很可能產生完全相同的代碼。

你可以採取的額外的精度long long優勢是保證提供（至少63值位）：

int m = (long long)n * (n + 1)/2;

這是否是比測試版本或多或少的效率將取決於目標CPU上編譯器版本和選項。這個版本更易於閱讀和理解，這很有價值。添加評論來解釋爲什麼結果將在範圍內將是有用的。

從由Amadeus的一個建議派生，這裏是一個更加簡潔，但要少得多可讀替代方案中，不使用64位算術：

int m = (n + (n & 1))/2 * (n + 1 - (n & 1));

演示：

如果n是奇數，我們得到m = (n + 1)/2 * n;
如果n是偶數，我們得到：m = n/2 * (n + 1);。

來源

2017-09-17 17:05:48 chqrlie

嚴格說來，最後一部分是_explanation_或_demonstration_，而不是一個「證明」，但這有些迂腐，因爲這裏不需要數學證明。 – Clifford

@Clifford：謝謝你的證明閱讀;-) – chqrlie

和一種或多種：

int m = (n/2 * n) + ((n%2) * (n/2)) + (n/2) + (n%2);

來源

2017-09-17 17:28:05 Serge

也許

result = (n) * (n/2) + (n & 1) * (n) + n/2 ;

來源

2017-09-17 17:37:10

任何簡明的方式來計算出n *（N + 1）/ 2和處理溢出同時

回答

相關問題