我正在寻找一个在Java中工作的有效公式,该公式可以计算以下表达式:

(low + high) / 2

用于二进制搜索。
到目前为止,我一直在使用“低+(高-低)/2”和“高-(高-低)/2”
在某些情况下避免上溢和下溢,但不能同时避免。
现在,我正在寻找一种有效的方法来执行此操作,该方法适用于任何整数(假设整数范围为-MAX_INT-1到MAX_INT)。

UPDATE :
结合Jander和Peter G.的答案,并进行了一段时间的实验,我得出了中间值元素及其直接邻居的以下公式:

最低中点(等于floor((low + high)/2),例如[2 3]-> 2,[2 4]-> 3,[-3 -2]-> -3)
mid = (low & high) + ((low ^ high) >> 1);

最高中点(等于ceil((low + high)/2),例如[2 3]-> 3,[2 4]-> 3,[-3 -2]-> -2)
low++;
mid = (low & high) + ((low ^ high) >> 1);

中点之前(等于floor((low + high - 1)/2)),例如[2 3]-> 2,[2 4]-> 2,[-7 -3]-> -6)
high--;
mid = (low & high) + ((low ^ high) >> 1);

后中点(等于ceil((low + high + 1)/2)),例如[2 3]-> 3,[2 4]-> 4,4,[-7 -3]-> -4)
mid = (low & high) + ((low ^ high) >> 1) + 1;

或者,在没有按位和(&)和或(|)的情况下,代码会稍微慢一些(可以用x >> 1替换floor(x / 2)以获得按位运算符自由的公式):

最左中点
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1);

最右边的中点
low++
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1);

中点之前
high--;
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1);

后中点
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1) + 1;

注意:上面的>>运算符被视为带符号移位。

最佳答案

http://aggregate.org/MAGIC/#Average%20of%20Integers:

(low & high) + ((low ^ high) / 2)

是两个无符号整数的防溢出平均值。

现在,此技巧仅适用于无符号整数。但是由于((a+x) + (b+x))/2 = (a+b)/2 + x,如果您具有与有符号整数相同的位大小的无符号整数,则可以按以下说明进行伪造:
unsigned int u_low  = low + MAX_INT + 1;
unsigned int u_high = high + MAX_INT + 1;
unsigned int u_avg  = (u_low & u_high) + (u_low ^ u_high)/2;
int avg = u_avg - MAX_INT - 1;

UPDATE :进一步考虑,即使您没有带符号的整数,这也将起作用。按位,有符号和无符号整数等效于加,减和 boolean 运算。因此,我们需要担心的是确保除法行为像无符号除法一样,我们可以通过使用shift并屏蔽掉最高位来做到这一点。
low += MAX+INT + 1;
high += MAX_INT + 1;
avg = (low & high) + (((low ^ high) >> 1) & MAX_INT);
avg -= MAX_INT + 1;

(请注意,如果您使用的是Java,则可以使用无符号移位... >>> 1而不是(... >> 1) & MAX_INT。)

然而,我偶然发现了一个更简单的选择,我还没有弄清楚它是如何工作的。无需通过MAX_INT调整数字或使用无符号变量或其他任何东西。很简单:
avg = (low & high) + ((low ^ high) >> 1);

已对范围为-32768..32767的16位带符号整数lowhigh的所有组合进行了测试,但尚未完全证明(无论如何,对我而言)。

10-07 19:03
查看更多