平均値を求め、オーバーフロー防止(整数のみ)

今日,C/C++における平均数オーバーフローを求める議論が見られた.そこで私はよく考えて関連資料を探しました.(a+b)/2,オーバーフローの源は加算がキャリー演算を生成する可能性があることを容易に発見し,キャリー演算を回避する方法を考えればよい.
キャリーを避けるために、私たちは自然にビット演算を考えることができます.a,bを2つの部分(バイナリの観点から)に分けることができ,1つは等しい共通部分であり,もう1つは等しくない部分である.平均数を計算するキャリーは主に等しい部分の加算によるものであることが分かったので,この共通部分を直接得ると,このキャリーを回避することができる.異なる部分を観察すると、1か0かのいずれかであることがわかります.異なる部分を2で割ると、異なる部分の平均値をとることができます.この2つの部分が加算され、私たちの平均値であることを簡単に発見しました.そこで平均数を計算するためにオーバーフローしない方法を見つけた.次に、いくつかの例を見てみましょう.

10       1010
14       1110
        ： 1010
      ： 0100
      2：0010
    = 1010(    ) + 0010(        ) = 1100
        12

以上の操作をビット演算で置き換えることができます.

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

これにより、整数加算によるオーバーフローを直接回避することができます.よく見ると、整数が奇数で偶数であれば、私たちの答えは下に整然としていることがわかります.したがって、必要に応じて、aとbのパリティの状況に応じて、手動で0.5を追加して答えを修正することができます.