安全整数中间值公式

Question

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

(low + high) / 2

用于二进制搜索.到目前为止,我一直在使用"低+(高 - 低)/ 2"和"高 - (高 - 低)/ 2"来避免某些情况下的溢出和下溢,但不是两者都有.现在我正在寻找一种有效的方法,可以用于任何整数(假设整数范围从-MAX_INT - 1到MAX_INT).

更新:结合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,[ - 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;

注意:上述>>运算符被认为是签名移位.

Answer 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;

更新:进一步思考,即使你没有签名整数,这也会有效.按位,有符号和无符号整数等效于加法,减法和布尔运算.所以我们需要担心的是确保除法的作用类似于无符号除法,我们可以通过使用移位和屏蔽最高位来实现.

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);

与16位有符号整数所有组合进行试验low,并high在范围内-32768..32767,但尚未完全成熟(由我反正).