任何简明的方式来计算出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和处理溢出同时

回答

相关问题