平均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,那么,当然,我失去了精度:

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

问题:有没有办法只计算long类型的使用,计算3个非常大的整数的截断平均值？不要将该问题视为C#特定的,只是我更容易在C#中提供样本.

Answer 1

这段代码可行,但不是那么漂亮.

它首先划分所有三个值(它将值置于底层,因此你"丢失"其余值),然后除以余数:

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);
}

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

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 4

您可以根据数字之间的差异计算数字的平均值,而不是使用总和.

假设x是最大值,y是中位数,z是最小值(正如你所知).我们称它们为max,median和min.

根据@ UlugbekUmirov的评论添加条件检查器:

long tmp = median + ((min - median) / 2);            //Average of min 2 values
if (median > 0) tmp = median + ((max - median) / 2); //Average of max 2 values
long mean;
if (min > 0) {
    mean = min + ((tmp - min) * (2.0 / 3)); //Average of all 3 values
} else if (median > 0) {
    mean = min;
    while (mean != tmp) {
        mean += 2;
        tmp--;
    }
} else if (max > 0) {
    mean = max;
    while (mean != tmp) {
        mean--;
        tmp += 2;
    }
} else {
    mean = max + ((tmp - max) * (2.0 / 3));
}

Answer 5

用supercat的修正修补Patrick Hofman的解决方案，我给你以下内容：

static Int64 Avg3 ( Int64 x, Int64 y, Int64 z )
{
    UInt64 flag = 1ul << 63;
    UInt64 x_ = flag ^ (UInt64) x;
    UInt64 y_ = flag ^ (UInt64) y;
    UInt64 z_ = flag ^ (UInt64) z;
    UInt64 quotient = x_ / 3ul + y_ / 3ul + z_ / 3ul
        + ( x_ % 3ul + y_ % 3ul + z_ % 3ul ) / 3ul;
    return (Int64) (quotient ^ flag);
}

和 N 元素情况：

static Int64 AvgN ( params Int64 [ ] args )
{
    UInt64 length = (UInt64) args.Length;
    UInt64 flag = 1ul << 63;
    UInt64 quotient_sum = 0;
    UInt64 remainder_sum = 0;
    foreach ( Int64 item in args )
    {
        UInt64 uitem = flag ^ (UInt64) item;
        quotient_sum += uitem / length;
        remainder_sum += uitem % length;
    }

    return (Int64) ( flag ^ ( quotient_sum + remainder_sum / length ) );
}

这总是给出平均值的 floor()，并消除所有可能的边缘情况。

Answer 6

因为C使用浮动除法而不是欧几里德除法,所以可能更容易计算三个无符号值的正确舍入平均值而不是三个有符号值.只需在取无符号平均值之前为每个数字添加0x8000000000000000UL,在获取结果后减去它,然后使用未经检查的强制转换Int64来获得有符号平均值.

要计算无符号平均值,请计算三个值的前32位的总和.然后计算三个值的底部32位的总和,再加上上面的和,再加上一个[加一是产生舍入结果].平均值将是第一笔金额的0x55555555倍,再加上第二笔金额的三分之一.

32位处理器的性能可能会通过产生三个"和"值来增强,每个值都是32位长,因此最终结果是((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; 它有可能会通过更换被进一步增强sumL/3与((sumL * 0x55555556UL) >> 32),尽管后者将取决于JIT优化[它可能知道如何通过3乘法替换一个部门,和它的代码实际上可能比显式乘法操作更高效.

Answer 7

如果你知道你有 N 个值，你能把每个值除以 N 并将它们相加吗？

long GetAverage(long* arrayVals, int n)
{
    long avg = 0;
    long rem = 0;

    for(int i=0; i<n; ++i)
    {
        avg += arrayVals[i] / n;
        rem += arrayVals[i] % n;
    }

    return avg + (rem / n);
}