low +（high-low）/ 2は（low + high）/ 2より安い

Question

私はmid要素を計算する必要があるバイナリ検索アルゴリズムを書いています。 2のような中間の要素を得る2つの方法があります。低+（高 - 低）/ 2（高+低）よりも効率的であると思わ

low+(high-low)/2 

と

(low+high)/2 

/2、どうして？

Answer 1

答えはhereです。

高値と低値が両方とも非負であると仮定して、最上位ビット（符号ビット）がゼロであることがわかっています。

したがって、高値と低値の両方が実際には31ビットの整数です。

high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 
low = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 

これらを一緒に追加すると、トップビットに「スピル」する可能性があります。

high + low =  1000 0000 0000 0000 0000 0000 0000 0000 
      = 2147483648 as unsigned 32-bit integer 
      = -2147483648 as signed 32-bit integer 

(high + low)/2 = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824 
(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824