C++ で 2 つの unsigned int を安全に平均するにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/3816446

  •  26-09-2019
  •  | 
  •  

質問

整数計算のみを使用して、C++ で 2 つの unsigned int を「安全に」平均したいと思います。

私が「安全に」と言っているのは、オーバーフロー (およびその他考えられるもの) を避けることです。

たとえば、平均化すると、 200 そして 5000 は簡単だ：

unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended

しかし、の場合には、 4294967295 そして 5000 それから：

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147

私が思いついた最高のものは次のとおりです。

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected

もっと良い方法はありますか？

役に立ちましたか？

解決

あなたの最後のアプローチが有望と思われます。手動でaとbの最下位ビットを考慮して、その上で改善することができます：

unsigned int average = (a / 2) + (b / 2) + (a & b & 1);

このケースとbの両方で正しい結果が奇数である。

与えます

他のヒント

unsigned int average = low + ((high - low) / 2);

編集

ここでは、関連記事があります： HTTP ：//googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.htmlする

あなたの方法は、両方の数字が奇数例えば5と7であれば、平均正しくない6ですが、あなたの方法＃3に戻り5ます。

これを試してみてください 

average = (a>>1) + (b>>1) + (a & b & 1)

数学演算子を持つだけます：

average = a/2 + b/2 + (a%2) * (b%2)

多少の x86 インライン アセンブリ (GNU C 構文) を気にしない場合は、supercat の提案を利用して次のことを行うことができます。 キャリー付き回転 加算後、完全な 33 ビットの結果の上位 32 ビットをレジスタに入れます。

もちろん、あなたは普段、 すべき inline-asm を使用すると一部の最適化が無効になるため、使用しないでください (https://gcc.gnu.org/wiki/DontUseInlineAsm）。しかし、とにかくここで行きましょう:

// works for 64-bit long as well on x86-64, and doesn't depend on calling convention
unsigned average(unsigned x, unsigned y)
{
    unsigned result;
    asm("add   %[x], %[res]\n\t"
        "rcr   %[res]"
        : [res] "=r" (result)   // output
        : [y] "%0"(y),  // input: in the same reg as results output.  Commutative with next operand
          [x] "rme"(x)  // input: reg, mem, or immediate
        :               // no clobbers.  ("cc" is implicit on x86)
    );
    return result;
}

の % 修飾子 引数が可換であることをコンパイラに伝えることは、実際には、y を定数またはポインタデリファレンス (メモリオペランド) として関数を呼び出して試した場合、より良い asm を作成するのに役立ちません。おそらく、出力オペランドに一致制約を使用すると、読み取り/書き込みオペランドでは使用できないため、これが無効になります。

ご覧のように Godbolt コンパイラ エクスプローラー上, 、これは正しくコンパイルされ、オペランドを次のように変更したバージョンも同様にコンパイルされます。 unsigned long, 、同じインライン ASM を使用します。ただし、clang3.9 はそれを台無しにし、 "m" のオプション "rme" 制約があるため、メモリに保存し、メモリ オペランドを使用します。

RCR-by-one はそれほど遅くはありませんが、Skylake では依然として 3 uop で、2 サイクルのレイテンシがあります。RCR の遅延がシングルサイクルである AMD CPU では最適です。（ソース： アグナー・フォグの命令表, も参照してください。 x86 パフォーマンス リンクのタグ Wiki)。@sellibitze のバージョンよりはまだ優れていますが、@Sheldon の順序依存バージョンよりは劣っています。(Godbolt のコードを参照)

ただし、インライン ASM は定数伝播などの最適化に勝てないため、その場合は純粋な C++ バージョンの方が優れていることに注意してください。

、正しい答えは...

であります 
(A&B)+((A^B)>>1)
何を持っていることは、それは3,3の平均は、私はあなたがすることを望んでいないことを推測している2であることを主張することをマイナーの詳細と、結構です。幸いなことに、簡単な修正があります：

unsigned int average = a/2 + b/2 + (a & b & 1);

これは単にバンプの両方の部門が切り捨てられたこと場合の平均バックアップます。

コードが埋め込まれたマイクロためのものである場合、および速度が重要である場合は、アセンブリ言語は、有用であり得ます。多くのマイクロコントローラでは、追加の結果は当然キャリーフラグに行くだろう、との命令はレジスタにそれをバックにシフトするために存在します。 ARMに、平均操作（ソースおよびDESTレジスタには）2つの命令で行うことができます。任意のC言語の等価は、おそらく、おそらく公正ビット以上より、少なくとも5をもたらす、となります。

ところで、短いワードサイズのマシンで、違いはさらに大きくなる可能性があります。 8ビットPIC-18シリーズで、平均2つの32ビット数は、12個の命令を取ります。シフトを行う、追加、および補正、5つの各シフトするための指示、追加のための8、および訂正のための8を取ると、26ので（ない非常に2.5倍の違いが、絶対的には、おそらくもっと重要）。

(((a&b << 1) + (a^b)) >> 1)も良い方法です。

提供： http://www.ragestorm.net/blogs/?p=29 

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

この試験のために== 5.0平均を期待

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top