任何简明的方式来计算出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);
}
有没有更简洁的方式来做到这一点?
答
你怎么看待:
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;
答
有使用三元运算符来编写测试更简洁的方式:
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);
。
答
和一种或多种:
int m = (n/2 * n) + ((n%2) * (n/2)) + (n/2) + (n%2);
答
也许
result = (n) * (n/2) + (n & 1) * (n) + n/2 ;
'长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 –