安全整数中间值公式
我正在寻找一个在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;
注意 ：上面的>>运算符被认为是签名移位。
来自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);
在-32768..32767范围内测试了low和high的16位有符号整数的所有组合，但尚未完全certificate（无论如何我都是）。
int half_low = low/2; int lsb_low = low - 2*half_low; int half_high = high/2; int lsb_high = high - 2*half_high; int mean = half_low + half_high + (lsb_low + lsb_high)/2;
假设high >= low ，您的初始方法的变体也应该起作用，即：
low + ((high - low) >>> 1)
其中>>>是无符号移位（如在Java中）。
这个想法是，如果结果被解释为无符号整数，则high - low永远不会溢出，因此无符号移位正确地执行除以2，并且公式计算中间值。
请注意，您的想法都不适用于low=-MAX_INT-1, high=MAX_INT 。 我能得到的最好的是low/2 + high/2 + ((low & 1) + (high & 1))/2 。