长数组的精确和 [英] Exact sum of a long array

问题描述

为了获得 long[] 的确切总和，我使用了以下代码段.

In order to get the exact sum of a long[] I'm using the following snippet.

public static BigInteger sum(long[] a) {
    long low = 0;
    long high = 0;
    for (final long x : a) {
        low += (x & 0xFFFF_FFFFL);
        high += (x >> 32);
    }
    return BigInteger.valueOf(high).shiftLeft(32).add(BigInteger.valueOf(low));
}

通过处理分成两半的数字并最终组合部分总和，它可以正常工作.令人惊讶的是，这种方法也有效:

It works fine by processing the numbers split in two halves and finally combining the partial sums. Surprisingly, this method works too:

public static BigInteger fastestSum(long[] a) {
    long low = 0;
    long high = 0;
    for (final long x : a) {
        low += x;
        high += (x >> 32);
    }
    // We know that low has the lowest 64 bits of the exact sum.
    // We also know that BigInteger.valueOf(high).shiftLeft(32) differs from the exact sum by less than 2**63.
    // So the upper half of high is off by at most one.
    high >>= 32;
    if (low < 0) ++high; // Surprisingly, this is enough to fix it.
    return BigInteger.valueOf(high).shiftLeft(64).add(BigInteger.valueOf(low));
}

我不相信fastestSum应该按原样工作.我相信它可以工作，但在最后一步还需要做更多的事情.但是，它通过了我的所有测试(包括大型随机测试).所以我问:有人能证明它有效或找到反例吗?

I don't believe that the fastestSum should work as is. I believe that it can work, but that something more has to be done in the final step. However, it passes all my tests (including large random tests). So I'm asking: Can someone prove that it works or find a counterexample?

推荐答案

fastestSum(new long[]{+1, -1})  => -18446744073709551616

这篇关于长数组的精确和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！