オーバーフローなしで2つの unsigned int の平均を求める

 (devblogs.microsoft.com)
9 ポイント 投稿者 xguru 2022-02-10 | 1件のコメント | WhatsAppで共有
  • 足して 2 で割る方法ではオーバーフローが発生する

→ (a + b) / 2

  • どちらが大きい数かわかっていれば、2 つの値の差を小さい方に加えて 2 で割ることもできる

→ low + (high - low) / 2

  • どちらが大きいかわからなくても使えるアルゴリズムは、2016 年に特許が失効した

→ (a / 2) + (b / 2) + (a & b & 1)

  • SWAR : SIMD within a register

→ (a & b) + (a ^ b) / 2

  • コンパイラが 64 ビットをサポートしているならキャストする

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

  • そしてその次はプロセッサ別のアセンブリコードです……原文を参照してください

関連記事

1件のコメント

 
xguru 2022-02-10

レイモンド・チェンのブログ The Old New Thing では、Windows 開発の舞台裏からさまざまなテーマまで扱っています。

日本では『レイモンド・チェンの Windows 開発 282 ストーリー』という翻訳書が出版されていましたが、現在は絶版です。