java - 安全整数中值公式

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;

或者，不用bitwise and (&) and or (|)，稍微慢一点的代码(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);

在 -32768..32767 范围内测试了 16 位有符号整数 low 和 high 的所有组合，但尚未完全证明(无论如何由我)。