快速平均而不分裂

Question

我有一个二进制搜索循环,它在执行路径中被多次命中.

剖析器显示搜索的划分部分(找到给定搜索范围的高和低索引的中间索引)实际上是搜索中最昂贵的部分,大约为4.

(我认为)有效的二进制搜索找到确切的中间值并不重要,只是中间附近的值,在任何一个方向都没有偏差.

是否有一个有点笨拙的算法来mid = (low + high) / 2更快地替换某些东西？

编辑:语言是C#,但是等效的位操作在任何语言中都有效(尽管它可能没有性能优势),这就是我离开C#标签的原因.

Answer 1

这是一个不受溢出问题影响的平均值的黑客版本:

unsigned int average (unsigned int x, unsigned int y)
{
  return (x&y)+((x^y)>>1);
}

Answer 2

int mid = (low + high) >>> 1;

请注意,当整数溢出成为问题时,使用"(低+高)/ 2"进行中点计算将无法正常工作.

Answer 3

您可以使用位移并克服可能的溢出问题:

low + ((high-low) >> 1)

但是我必须承认,我希望现代编译器和解释器将2除(或除以2的任何其他常数幂)除以位移,因此不确定它是否真的有用 - 试试看.

Answer 4

为了进一步扩展Nils的回答,Richard Schroeppel发明了这一点.

http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23

第23项(Schroeppel):

(A和B)+(A OR B)= A + B =(A XOR B)+ 2(A和B).

(A + B)/2 = ((A XOR B) + 2(A AND B))/2
          =  (A XOR B)/2  + (A AND B)
          =  (A XOR B)>>1 + (A AND B)


avg(x,y){return((x^y)>>1)+(x&y);}

(A AND B) + (A OR B) = A + B因为A AND B给出了共享(A和B之间)两个幂的总和,A OR B给出了共享的那些和那些不共享的那些,因此:

(A AND B) + (A OR B) = 
   (sum of shared powers of two) + 
   ((sum of shared powers of two) + (sum of unshared powers of two)) = 
     (sum of shared powers of two) + 
     ((sum of shared powers of two) + (sum of powers of two of A only) + 
     (sum of powers of two of B only)) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B. 

A XOR B 给出了A和B之间不同位的映射.因此,

A XOR B = (sum of powers of two of A only) + (sum of powers of two of B only). 

因此:

2(A AND B) + (A XOR B) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B.