3个长整数的平均值

Question

我有3个非常大的有符号整数。

long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;

我想计算它们的截断平均值。预期平均值是long。MaxValue-1，即9223372036854775806。

不可能计算为：

long avg = (x + y + z) / 3; // 3074457345618258600

注：我读了所有关于2个数字的平均值的问题，但我不知道该技术如何应用于3个数字的平均值。

使用BigInteger将非常容易，但假设我不能使用它。

BigInteger bx = new BigInteger(x);
BigInteger by = new BigInteger(y);
BigInteger bz = new BigInteger(z);
BigInteger bavg = (bx + by + bz) / 3; // 9223372036854775806

如果我转换为双精度，那么，当然，我会失去精度：

double dx = x;
double dy = y;
double dz = z;
double davg = (dx + dy + dz) / 3; // 9223372036854780000

如果我转换为decimal，它可以工作，但也让我们假设我不能使用它。

decimal mx = x;
decimal my = y;
decimal mz = z;
decimal mavg = (mx + my + mz) / 3; // 9223372036854775806

问题：有没有一种方法可以仅使用长类型来计算3个非常大整数的截断平均值？不要认为这个问题是C语言特有的，只是我更容易用C语言提供示例。

Answer 1

Patrick Hofman发布了一个很棒的解决方案。但如果需要，它仍然可以通过其他几种方式实现。使用这里的算法，我有另一个解决方案。如果仔细实施，它可能比硬件除数慢的系统中的多个除法更快。它可以通过使用除法常量技术进一步优化，黑客很高兴

public class int128_t {
    private int H;
    private long L;

    public int128_t(int h, long l)
    {
        H = h;
        L = l;
    }

    public int128_t add(int128_t a)
    {
        int128_t s;
        s.L = L + a.L;
        s.H = H + a.H + (s.L < a.L);
        return b;
    }

    private int128_t rshift2()  // right shift 2
    {
        int128_t r;
        r.H = H >> 2;
        r.L = (L >> 2) | ((H & 0x03) << 62);
        return r;
    }

    public int128_t divideby3()
    {
        int128_t sum = {0, 0}, num = new int128_t(H, L);
        while (num.H || num.L > 3)
        {
            int128_t n_sar2 = num.rshift2();
            sum = add(n_sar2, sum);
            num = add(n_sar2, new int128_t(0, num.L & 3));
        }

        if (num.H == 0 && num.L == 3)
        {
            // sum = add(sum, 1);
            sum.L++;
            if (sum.L == 0) sum.H++;
        }
        return sum; 
    }
};

int128_t t = new int128_t(0, x);
t = t.add(new int128_t(0, y));
t = t.add(new int128_t(0, z));
t = t.divideby3();
long average = t.L;

在64位平台上的C/C中，使用__int128要容易得多

int64_t average = ((__int128)x + y + z)/3;

Answer 2

NB-帕特里克已经给出了一个很好的答案。在此基础上扩展，您可以对任意数量的整数执行通用版本，如下所示：

long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;

long[] arr = { x, y, z };
var avg = arr.Select(i => i / arr.Length).Sum() 
        + arr.Select(i => i % arr.Length).Sum() / arr.Length;

Answer 3

这段代码可以工作，但不是那么漂亮。

它首先将所有三个值相除（它将值分层，因此您将“丢失”余数），然后将余数相除：

long n = x / 3
         + y / 3
         + z / 3
         + ( x % 3
             + y % 3
             + z % 3
           ) / 3

注意，当有一个或多个负值时，上述样本并不总是正常工作。

正如与Ulugbek讨论的那样，由于下面的评论数量呈爆炸式增长，因此这是当前正值和负值的最佳解决方案。

感谢Ulugbek Umirov， James S， KevinZ， Marc van Leeuwen， gnasher729的回答和评论，这是当前的解决方案：

static long CalculateAverage(long x, long y, long z)
{
    return (x % 3 + y % 3 + z % 3 + 6) / 3 - 2
            + x / 3 + y / 3 + z / 3;
}

static long CalculateAverage(params long[] arr)
{
    int count = arr.Length;
    return (arr.Sum(n => n % count) + count * (count - 1)) / count - (count - 1)
           + arr.Sum(n => n / count);
}