快速平均，无需除法

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;

请注意，使用“(low + high) / 2”进行中点计算 将无法正常工作。

Answer 3

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

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

但是我必须承认我希望现代编译器和解释器将除以 2（或除以任何其他 2 的常数幂）作为位移位，所以不确定它是否会真的有帮助 - 尝试一下。

Answer 4

为了进一步扩展尼尔斯的答案，理查德·施罗佩尔发明了这个。

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

第 23 项（Schroeppel）：

（A 和 B）+（A 或 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 给出了 2 的共享（A 和 B 之间）幂的总和，< code>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.

Answer 5

如果我没记错的话，在某些情况下，使用数组的中间位置实际上会更慢。 解决方案是随机选择平分数组的索引。 确定数组中位数的算法同样如此。

我不记得确切的细节，但我记得在 iTunes 上的 MIT 算法系列。

Answer 6

尝试低 + ((高 - 低) / 2))。 这应该有效，因为您只取两个数字的平均值。 如果二分搜索列表相当大，这将减少算法所花费的时间，因为高 - 低比高 + 低要小得多。