13

x と y があり、どちらも C の符号付き整数であるとしましょう。2 つの間の最も正確な平均値をどのように見つければよいでしょうか?

マシン/コンパイラ/ツールチェーン固有の仕組みを利用しないソリューションを希望します。

私が思いついた最善の方法は次のとおり(a / 2) + (b / 2) + !!(a % 2) * !!(b %2)です。より正確な解決策はありますか? もっと早く?もっと簡単?

一方が他方よりも先験的に大きいかどうかがわかっている場合はどうなりますか?

ありがとう。

D


編集者注int: 入力値が C型の最大絶対境界に近い場合、OP は整数オーバーフローの影響を受けない回答を期待することに注意してください。これは元の質問には記載されていませんが、回答する際に重要です。

4

7 に答える 7

9

回答を受け入れた後 (4 年間)

1.とのすべての組み合わせに対して の 範囲全体で動作しint average_int(int a, int b)ます。2.より広い数学を使用しているか のように、 と同じ結果が得られます。
[INT_MIN..INT_MAX]ab
(a+b)/2

int2xが存在する場合、@ Santiago Alessandriアプローチはうまく機能します。

int avgSS(int a, int b) {
  return (int) ( ((int2x) a + b) / 2);
}

それ以外の場合は@AProgrammerのバリエーション:
注: より広い数学は必要ありません。

int avgC(int a, int b) {
  if ((a < 0) == (b < 0)) {  // a,b same sign
    return a/2 + b/2 + (a%2 + b%2)/2;
  }
  return (a+b)/2;
}

より多くのテストを行うが、テストを行わないソリューション%

(a+b)/2以下のすべての解決策は、オーバーフローが発生しなかったときに 1 以内で「機能」しまし たが(a+b)/2、すべてに一致するものを見つけたいと思っていましintた。


@Santiago Alessandriintソリューションは、範囲が範囲よりも狭い限り機能しますlong long-通常はそうです。

((long long)a + (long long)b) / 2

受け入れられた答えである@AProgrammerは、約 1/4 の時間で match に失敗します(a+b)/2。次のような入力例a == 1, b == -2

a/2 + b/2 + (a%2 + b%2)/2

@Guy Sirton、ソリューションは約1/8の時間で一致に失敗します(a+b)/2。次のような入力例a == 1, b == 0

int sgeq = ((a<0)==(b<0));
int avg = ((!sgeq)*(a+b)+sgeq*(b-a))/2 + sgeq*a;

@R ..、ソリューションは約1/4の時間で一致に失敗します(a+b)/2。次のような入力例a == 1, b == 1

return (a-(a|b)+b)/2+(a|b)/2;

@MatthewD、現在削除されたソリューションは、一致する時間の約 5/6 に失敗します(a+b)/2。次のような入力例a == 1, b == -2

unsigned diff;
signed mean;
if (a > b) {
    diff = a - b;
    mean = b + (diff >> 1);
} else {
    diff = b - a;
    mean = a + (diff >> 1);
}
于 2015-04-23T20:55:00.797 に答える
3

オーバーフローを恐れずにそのまま(a^b)<=0使用できれば。(a+b)/2

それ以外の場合は、を試してください(a-(a|b)+b)/2+(a|b)/2。は少なくとも両方と-(a|b)同じ大きさであり、反対の符号を持つため、オーバーフローを回避できます。ab

私はこれを頭のてっぺんからすばやく行ったので、いくつかの愚かなエラーがあるかもしれません。ここにはマシン固有のハックはないことに注意してください。すべての動作は、C標準と、符号付き値の2の補数、1の補数、または符号の大きさの表現が必要であり、ビット単位の演算子がビットごとの表現で機能することを指定するという事実によって完全に決定されます。いいえ、の相対的な大きさa|bは表現によって異なります。

編集:a+(b-a)/2同じ記号の場合にも使用できます。これにより、にバイアスがかかることに注意してくださいa。あなたはそれを逆転させて、へのバイアスを得ることができますb。一方、上記の私の解決策は、私が間違っていなければ、ゼロに向かってバイアスを与えます。

別の試み: 1つの標準的なアプローチは(a&b)+(a^b)/2です。2の補数では、符号に関係なく機能しますが、同じ符号がある場合はa、1の補数または符号の大きさでも機能すると思います。b気になりますか?

于 2011-04-18T00:53:58.923 に答える
3

編集: @chux によって修正されたバージョン - モニカの復活:

if ((a < 0) == (b < 0)) {  // a,b same sign
  return a/2 + b/2 + (a%2 + b%2)/2;
} else {
  return (a+b)/2;
}

元の回答(受け入れられなかったら削除していたでしょう)。

a/2 + b/2 + (a%2 + b%2)/2

実装特性に関する仮定なしの法案に適合する最も単純なもののようです(C90の実装に依存していたのに対し、/の結果を「0に向かって切り捨てられた」と指定するC99に依存しています)。

これには、テストがない (したがってコストのかかるジャンプがない) という利点があり、すべての除算/剰余は 2 であるため、コンパイラによるビット調整手法の使用が可能です。

于 2011-04-18T09:29:15.620 に答える
1

役立つかもしれないいくつかの観察:

「最も正確」は必ずしも整数で一意であるとは限りません。たとえば、1 と 4 の場合、2 と 3 は等しく「最も正確な」回答です。数学的に (C 整数ではありません):

(a+b)/2 = a+(b-a)/2 = b+(a-b)/2

これを分解してみましょう:

  • sign(a)!=sign(b) の場合、a+b はオーバーフローしません。このケースは、2 の補数表現の最上位ビットを比較することで判断できます。
  • sign(a)==sign(b) の場合、a が b より大きい場合、(ab) はオーバーフローしません。それ以外の場合 (ba) はオーバーフローしません。編集:実際にはどちらもオーバーフローしません。

正確に何を最適化しようとしていますか? プロセッサ アーキテクチャが異なれば、最適なソリューションも異なる場合があります。たとえば、コードで乗算を AND に置き換えると、パフォーマンスが向上する場合があります。また、2 の補数アーキテクチャでは、単純に (a & b & 1) を実行できます。

速すぎるようには見えませんが、おそらく誰かが使用して改善できるコードをいくつか投げ出します。

int sgeq = ((a<0)==(b<0));
int avg = ((!sgeq)*(a+b)+sgeq*(b-a))/2 + sgeq*a
于 2011-04-18T02:46:55.060 に答える
1

符号なし整数の場合、平均は (x+y)/2 の下限です。しかし、符号付き整数についても同じことが失敗します。この式は、下限が平均よりも 1 小さいため、合計が奇数の整数では失敗します。

詳細については、Hacker's Delightのセクション 2.5 を参照してください。

オーバーフローなしで 2 つの符号付き整数の平均を計算するコードは次のとおりです。

int t = (a & b) + ((a ^ b) >> 1)
unsigned t_u = (unsigned)t
int avg = t + ( (t_u >> 31 ) & (a ^ b) )

Z3 SMTソルバーを使用して正確性を確認しました

于 2016-03-16T20:56:38.150 に答える
-1

私はこれを行い、両方をlong long(64ビット符号付き整数)に変換して合計します。これはオーバーフローせず、結果を2で除算します。

((long long)a + (long long)b) / 2

小数部分が必要な場合は、doubleとして格納します。

結果は32ビット整数に収まることに注意することが重要です。

最高ランクの整数を使用している場合は、次を使用できます。

((double)a + (double)b) / 2
于 2011-04-18T00:54:10.300 に答える
-2

この答えは、任意の数の整数に適合します。

    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    decimal avg = 0;
    for (int i = 0; i < array.Length; i++){
        avg = (array[i] - avg) / (i+1) + avg;
    }

このテストでは avg == 5.0 が期待されます

于 2016-12-22T22:08:27.737 に答える