快速平均而无除法 [英] Fast average without division

问题描述

我有一个二进制搜索循环，该循环在执行路径中被击中多次.

I have a binary search loop which gets hit many times in the execution path.

分析器显示搜索的划分部分(根据搜索范围的高低索引找到中间索引)实际上是搜索成本最高的部分，大约是4倍.

A profiler shows that the division part of the search (finding the middle index given the high and low indices of the search range) is actually the most costly part of the search, by a factor of about 4.

(我认为)，对于有效的二进制搜索来说，找到确切的中间值并不重要，只是找到一个接近中间值的值，而该值在任一方向上都没有偏差.

(I think) it is not critical for efficient binary search to find the exact middle value, just a value near the middle which does not have bias in either direction.

是否有位纠缠算法用更快的速度替换mid = (low + high) / 2?

Is there a bit-twiddling algorithm to replace mid = (low + high) / 2 with something much faster?

语言是C#，但是等效的位操作在任何语言中都是有效的(尽管可能对性能没有好处)，这就是为什么我不使用C#标记的原因.

Language is C#, but the equivalent bit-operation is valid in any language (although it may be of no performance benefit), which is why I left the C# tag off.

推荐答案

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

请注意，使用((低+高)/2")进行中点计算

Be advised that using "(low + high) / 2" for midpoint calculations won't work correctly when integer overflow becomes an issue.

这篇关于快速平均而无除法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！