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
问题：有没有办法只用longtypes来计算3个超大整数的截尾平均值？ 不要认为这个问题是C＃特有的，只是在C＃中提供示例更容易。
这个代码可以工作，但不是那么漂亮。
它首先将所有三个值分开（它将数值设置为底数，所以您将丢失余数），然后除以余数：
long n = x / 3 + y / 3 + z / 3 + ( x % 3 + y % 3 + z % 3 ) / 3
请注意，上面的示例有一个或多个负值时不总是正常工作。
正如Ulugbek所讨论的那样，由于评论的数量在下面爆炸，所以这里是正面和负面价值的最佳解决scheme。
感谢Ulugbek Umirov ， James S ， KevinZ ， Marc van Leeuwen ， gnasher729的回答和评论，这是目前的解决scheme：
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 – 帕特里克已经给出了一个很好的答案 。 扩大这个你可以做任何数量的整数的通用版本，如下所示：
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已经发布了一个很好的解决scheme 。 但是如果需要的话，还可以通过其他几种方式来实现。 在这里使用algorithm，我有另一种解决scheme。 如果仔细实施，可能会比硬件除数缓慢的系统中的多个部门更快。 通过使用黑客喜悦的常量技术进一步优化
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; sL = L + aL; sH = H + aH + (sL < aL); return b; } private int128_t rshift2() // right shift 2 { int128_t r; rH = H >> 2; rL = (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 = tL;
在64位平台上的C / C ++中，使用__int128更容易
int64_t average = ((__int128)x + y + z)/3;
您可以根据数字之间的差异来计算数字的均值，而不是使用总和。
假设x是最大值，y是中值，z是最小值（如你所见）。 我们将他们称为最大值，中位数和最小值。
根据@ 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)); }
你可以使用这样的事实，你可以写每个数字为y = ax + b ，其中x是一个常数。 每个a都是y / x （该部分的整数部分）。 每个b将是y % x （该部门的其余部分/模）。 如果以智能的方式select这个常数，例如通过select最大数的平方根作为常量，就可以得到x数的平均值而不会出现溢出问题。
一个任意的数字列表的平均值可以通过查找：
( ( sum( all A's ) / length ) * constant ) + ( ( sum( all A's ) % length ) * constant / length) + ( ( sum( all B's ) / length )
其中%表示模和和/表示分割的“整体”部分。
该程序看起来像这样：
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 ); } }
由于C使用的是分区而不是欧几里德分区，因此计算三个无符号值的适当舍入平均值可能比三个无符号值的计算更容易。 在取无符号平均值之前，只需将0x8000000000000000UL添加到每个数字，在得到结果之后减去它，并使用未选中的转换回Int64以获得带符号的平均值。
要计算无符号平均值，计算三个值的前32位的和。 然后计算三个值的底部32位的和，加上上面的和，再加上一个[加1就是舍入结果]。 平均值将是第一笔总和的0x55555555倍，再加上第二笔的三分之一。
最终结果是((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3 ;可以通过产生三个“和”值来增强32位处理器上的性能。 ((sumL * 0x55555556UL) >> 32)replacesumL/3可能会进一步增强，尽pipe后者将取决于JIT优化器[它可能知道如何用乘法replace除数3，并且其代码实际上可能比明确的乘法运算更有效]。
为了解决帕特里克·霍夫曼 （ Patrick Hofman ）的解决scheme，我给了你以下的build议：
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 ) ); }
这总是给出平均值（），并消除每一个可能的边缘情况。
如果你知道你有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); }
这个函数计算两个部门的结果。 它应该很好地概括其他除数和字的大小。
它通过计算双字加法结果进行工作，然后进行分解。
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
码
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)); }
我也尝试过，并提出了一个更快的解决scheme（虽然只是一个3/4的因素）。 它使用一个单独的部门
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; }
其中smallDiv3使用乘法除以3，只对小的参数工作
private static long smallDiv3(long n) { assert -30 <= n && n <= 30; // Constants found rather experimentally. return (64/3*n + 10) >> 6; }
这里是整个代码，包括一个testing和一个基准， 结果并不令人印象深刻。
尝试这个：
long n = Array.ConvertAll(new[]{x,y,z},v=>v/3).Sum() + (Array.ConvertAll(new[]{x,y,z},v=>v%3).Sum() / 3);
