我有3个非常大的有符号整数。
long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;
我想计算它们的截断平均值。预期平均值为9223372036854775806
的long.MaxValue - 1
。
它不可能计算为:
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#提供示例对我来说更容易。
发布于 2014-05-30 16:05:13
这段代码可以工作,但并不美观。
它首先将所有三个值相除(它对这些值求底,因此您将“丢失”余数),然后将余数相除:
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);
}
发布于 2014-05-30 16:20:02
注意-帕特里克已经给了a great answer。在此基础上,您可以为任意数量的整数创建一个通用版本,如下所示:
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;
发布于 2014-05-30 21:08:23
帕特里克·霍夫曼报道了posted a great solution。但如果需要,它仍然可以通过其他几种方式实现。使用here算法,我有了另一个解决方案。如果仔细实现,它可能会比具有缓慢硬件因子的系统中的多个分区更快。通过使用divide by constants技术,可以从黑客的喜好中进一步优化它
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;
https://stackoverflow.com/questions/23949785
复制相似问题