45

整数演算だけを使用して、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

より良い方法はありますか？

4

10 に答える 10

55

あなたの最後のアプローチは有望に思えます。a と b の最下位ビットを手動で検討することで、これを改善できます。

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

これにより、a と b の両方が奇数の場合に正しい結果が得られます。

于 2010-09-28T19:47:34.747 に答える
29

どちらが高いかを事前に知っていれば、非常に効率的な方法が可能です。それ以外の場合は、これを使用するために条件付きで交換するのではなく、他の戦略のいずれかを使用することをお勧めします。

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

関連記事はこちら: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

于 2010-09-28T19:47:30.863 に答える
18

両方の数値が奇数、たとえば 5 と 7、平均が 6 の場合、メソッドは正しくありませんが、メソッド #3 は 5 を返します。

これを試して：

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

数学演算子のみ:

average = a/2 + b/2 + (a%2) * (b%2)
于 2010-09-28T19:48:11.523 に答える
9

そして正解は...

(A&B)+((A^B)>>1)
于 2013-02-14T21:53:46.907 に答える
9

少しの x86 インライン アセンブリ (GNU C 構文) を気にしない場合は、完全な 33 ビットの結果の上位 32 ビットをレジスタに入れるために、加算の後に、rotate-with-carryを使用するという supercat の提案を利用できます。.

もちろん、通常は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;
}

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

Godbolt コンパイラーの explorerでわかるように、これは正しくコンパイルさunsigned longれ、同じインライン asm でオペランドを に変更したバージョンも同様にコンパイルされます。ただし、clang3.9 はそれを混乱させ"m"、制約にオプションを使用することを決定するため"rme"、メモリに格納してメモリ オペランドを使用します。

RCR-by-one はそれほど遅くはありませんが、Skylake では 2 サイクルのレイテンシで 3 uops です。これは、RCR のレイテンシが 1 サイクルである AMD CPU に最適です。(出典: Agner Fog の命令表、x86 パフォーマンス リンクについてはタグ wikiも参照してください)。@sellibitze のバージョンよりも優れていますが、@Sheldon の順序依存バージョンよりも劣っています。(Godbolt のコードを参照)

ただし、inline-asm は定数伝播などの最適化を無効にするため、その場合は純粋な C++ バージョンの方が優れていることに注意してください。

于 2010-09-28T21:19:28.467 に答える
4

あなたが持っているものは問題ありません.3と3の平均が2であると主張するというマイナーな詳細があります.私はあなたがそれを望んでいないと推測しています. 幸いなことに、簡単な修正があります。

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

これは、両方の部門が切り捨てられた場合に、平均を元に戻すだけです。

于 2010-09-28T19:48:03.467 に答える
2

コードが組み込みマイクロ用で、速度が重要な場合は、アセンブリ言語が役立つ場合があります。多くのマイクロコントローラでは、加算の結果は当然キャリー フラグに入り、それをレジスタに戻す命令が存在します。ARM では、平均的な操作 (レジスタ内のソースと宛先) は 2 つの命令で実行できます。同等の C 言語は、おそらく少なくとも 5、おそらくそれよりもかなり多く生成されます。

ちなみに、ワードサイズが短いマシンでは、違いがさらに大きくなる可能性があります。8 ビットの PIC-18 シリーズでは、2 つの 32 ビット数を平均するには 12 命令が必要です。シフト、追加、修正を行うには、シフトごとに 5 つの命令、追加に 8 つ、修正に 8 つの命令が必要になるため、26 (2.5 倍の差ではありませんが、絶対的にはより重要です)。

于 2010-09-28T20:37:57.553 に答える
-3 
    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-22T21:59:35.723 に答える
-4

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

礼儀: http://www.ragestorm.net/blogs/?p=29

于 2012-03-12T03:24:37.033 に答える