3个长整数的平均值

我有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 # 提供示例更容易。

10225 次浏览
小开
最佳答案

This code will work, but isn't that pretty.

It first divides all three values (it floors the values, so you 'lose' the remainder), and then divides the remainder:

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

Note that the above sample does not always work properly when having one or more negative values.

As discussed with Ulugbek, since the number of comments are exploding below, here is the current BEST solution for both positive and negative values.

Thanks to answers and comments of Ulugbek Umirov, James S, KevinZ, Marc van Leeuwen, gnasher729 this is the current solution:

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

NB - Patrick has already given a great answer. Expanding on this you could do a generic version for any number of integers like so:

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;
小开

Patrick Hofman has posted a great solution. But if needed it can still be implemented in several other ways. Using the algorithm here I have another solution. If implemented carefully it may be faster than the multiple divisions in systems with slow hardware divisors. It can be further optimized by using divide by constants technique from hacker's delight

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;

In C/C++ on 64-bit platforms it's much easier with __int128

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

You can calculate the mean of numbers based on the differences between the numbers rather than using the sum.

Let's say x is the max, y is the median, z is the min (as you have). We will call them max, median and min.

Conditional checker added as per @UlugbekUmirov's comment:

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

Because C uses floored division rather than Euclidian division, it may easier to compute a properly-rounded average of three unsigned values than three signed ones. Simply add 0x8000000000000000UL to each number before taking the unsigned average, subtract it after taking the result, and use an unchecked cast back to Int64 to get a signed average.

To compute the unsigned average, compute the sum of the top 32 bits of the three values. Then compute the sum of the bottom 32 bits of the three values, plus the sum from above, plus one [the plus one is to yield a rounded result]. The average will be 0x55555555 times the first sum, plus one third of the second.

Performance on 32-bit processors might be enhanced by producing three "sum" values each of which is 32 bits long, so that the final result is ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; it might possibly be further enhanced by replacing sumL/3 with ((sumL * 0x55555556UL) >> 32), though the latter would depend upon the JIT optimizer [it might know how to replace a division by 3 with a multiply, and its code might actually be more efficient than an explicit multiply operation].

小开

You could use the fact that you can write each of the numbers as y = ax + b, where x is a constant. Each a would be y / x (the integer part of that division). Each b would be y % x (the rest/modulo of that division). If you choose this constant in an intelligent way, for example by choosing the square root of the maximum number as a constant, you can get the average of x numbers without having problems with overflow.

The average of an arbitrary list of numbers can be found by finding:

( ( sum( all A's ) / length ) * constant ) +
( ( sum( all A's ) % length ) * constant / length) +
( ( sum( all B's ) / length )

where % denotes modulo and / denotes the 'whole' part of division.

The program would look something like:

class Program
{
static void Main()
{
List<long> list = new List<long>();
list.Add( long.MaxValue );
list.Add( long.MaxValue - 1 );
list.Add( long.MaxValue - 2 );


long sumA = 0, sumB = 0;
long res1, res2, res3;
//You should calculate the following dynamically
long constant = 1753413056;


foreach (long num in list)
{
sumA += num / constant;
sumB += num % constant;
}


res1 = (sumA / list.Count) * constant;
res2 = ((sumA % list.Count) * constant) / list.Count;
res3 = sumB / list.Count;


Console.WriteLine( res1 + res2 + res3 );
}
}
小开

Patching Patrick Hofman's solution with supercat's correction, I give you the following:

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

And the N element case:

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

This always gives the floor() of the mean, and eliminates every possible edge case.

小开

If you know you have N values, can you just divide each value by N and sum them together?

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

This function computes the result in two divisions. It should generalize nicely to other divisors and word sizes.

It works by computing the double-word addition result, then working out the division.

Int64 average(Int64 a, Int64 b, Int64 c) {
// constants: 0x10000000000000000 div/mod 3
const Int64 hdiv3 = UInt64(-3) / 3 + 1;
const Int64 hmod3 = UInt64(-3) % 3;


// compute the signed double-word addition result in hi:lo
UInt64 lo = a; Int64 hi = a>=0 ? 0 : -1;
lo += b; hi += b>=0 ? lo<b : -(lo>=UInt64(b));
lo += c; hi += c>=0 ? lo<c : -(lo>=UInt64(c));


// divide, do a correction when high/low modulos add up
return hi>=0 ? lo/3 + hi*hdiv3 + (lo%3 + hi*hmod3)/3
: lo/3+1 + hi*hdiv3 + Int64(lo%3-3 + hi*hmod3)/3;
}
小开

Math

(x + y + z) / 3 = x/3 + y/3 + z/3


(a[1] + a[2] + .. + a[k]) / k = a[1]/k + a[2]/k + .. + a[k]/k

Code

long calculateAverage (long a [])
{
double average = 0;


foreach (long x in a)
average += (Convert.ToDouble(x)/Convert.ToDouble(a.Length));


return Convert.ToInt64(Math.Round(average));
}


long calculateAverage_Safe (long a [])
{
double average = 0;
double b = 0;


foreach (long x in a)
{
b = (Convert.ToDouble(x)/Convert.ToDouble(a.Length));


if (b >= (Convert.ToDouble(long.MaxValue)-average))
throw new OverflowException ();


average += b;
}


return Convert.ToInt64(Math.Round(average));
}
小开

I also tried it and come up with a faster solution (although only by a factor about 3/4). It uses a single division

public static long avg(long a, long b, long c) {
final long quarterSum = (a>>2) + (b>>2) + (c>>2);
final long lowSum = (a&3) + (b&3) + (c&3);
final long twelfth = quarterSum / 3;
final long quarterRemainder = quarterSum - 3*twelfth;
final long adjustment = smallDiv3(lowSum + 4*quarterRemainder);
return 4*twelfth + adjustment;
}

where smallDiv3 is division by 3 using multipliation and working only for small arguments

private static long smallDiv3(long n) {
assert -30 <= n && n <= 30;
// Constants found rather experimentally.
return (64/3*n + 10) >> 6;
}

Here is the whole code including a test and a benchmark, the results are not that impressive.

小开

Try this:

long n = Array.ConvertAll(new[]{x,y,z},v=>v/3).Sum()
+  (Array.ConvertAll(new[]{x,y,z},v=>v%3).Sum() / 3);

提交答案