我正在寻找一个在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位带符号整数
low
和high
的所有组合进行了测试,但尚未完全证明(无论如何,对我而言)。