回答を受け入れた後 (4 年間)
1.とのすべての組み合わせに対して の
範囲全体で動作しint average_int(int a, int b)
ます。2.より広い数学を使用しているか
のように、 と同じ結果が得られます。
[INT_MIN..INT_MAX]
a
b
(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);
}