安全整数中间值公式 [英] Safe integer middle value formula

问题描述

我正在寻找一个在Java中工作的有效公式，它计算以下表达式：

I am looking for an efficient formula working in Java which calculates the following expression:

(low + high) / 2

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

which is used for binary search. So far, I have been using "low + (high - low) / 2" and "high - (high - low) / 2" to avoid overflow and underflows in some cases, but not both. Now I am looking for an efficient way to do this, which would for for any integer (assuming integers range from -MAX_INT - 1 to MAX_INT).

更新：
结合Jander和Peter G.的答案并尝试一段时间，我得到了以下中间值元素及其近邻的公式：

UPDATE: Combining the answers from Jander and Peter G. and experimenting a while I got the following formulas for middle value element and its immediate neighbors:

最低中点（等于楼层（（低+高）/ 2），例如[2 3] - > 2，[2 4] - > 3，[ - 3] - > -3）

Lowest-midpoint (equal to floor((low + high)/2), e.g. [2 3] -> 2, [2 4] -> 3, [-3 -2] -> -3)

mid = (low & high) + ((low ^ high) >> 1);

最高中点（等于 ceil（（低+高）/ 2 ），例如[2 3] - > 3，[2 4] - > 3，[ - 3 -2] - > -2）

Highest-midpoint (equal to ceil((low + high)/2), e.g. [2 3] -> 3, [2 4] -> 3, [-3 -2] -> -2)

low++;
mid = (low & high) + ((low ^ high) >> 1);

前中点（等于楼层（（低+高 - 1） / 2）），例如[2 3] - > 2，[2 4] - > 2，[ - 7 -3] - > -6）

Before-midpoint (equal to floor((low + high - 1)/2)), e.g. [2 3] -> 2, [2 4] -> 2, [-7 -3] -> -6)

high--;
mid = (low & high) + ((low ^ high) >> 1);

中后点（等于 ceil（（低+高+ 1） / 2）），例如[2 3] - > 3，[2 4] - > 4，[ - 7 -3] - > -4）

After-midpoint (equal to ceil((low + high + 1)/2)), e.g. [2 3] -> 3, [2 4] -> 4, [-7 -3] -> -4)

mid = (low & high) + ((low ^ high) >> 1) + 1;

或者，没有按位和（&）和或（|），代码稍慢（ x>> 1 可以替换为 floor（x / 2）以获取按位运算符免费公式）：

Or, without bitwise and (&) and or (|), slightly slower code (x >> 1 can be replaced with floor(x / 2) to obtain bitwise operator free formulas):

最左边 - 中点

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

After-midpoint

After-midpoint

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

注意：以上>> 运算符被认为是签名班次。

Note: the above >> operator is considered to be signed shift.

推荐答案

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

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

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

is an overflow-proof average of two unsigned integers.

现在，这个技巧仅适用于无符号整数。但是因为（（a + x）+（b + x））/ 2 =（a + b）/ 2 + x ，你可以按照以下方式捏造它，如果你具有与有符号整数相同位的无符号整数：

Now, this trick only works on unsigned integers. But because ((a+x) + (b+x))/2 = (a+b)/2 + x, you can fudge it as follows, if you have unsigned integers with the same bit size as your signed integers:

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: On further thought, this will work even if you don't have signed integers. Bitwise, signed and unsigned integers are equivalent over addition, subtraction, and Boolean operations. So all we need to worry about is making sure that divide acts like an unsigned divide, which we can do by using a shift and masking out the uppermost bit.

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 。）

(Note that if you're using Java, you can use an unsigned shift, ... >>> 1, instead of (... >> 1) & MAX_INT.)

但是，还有一个替代方案，我偶然发现它更简单，我还没弄清楚它是如何工作的。无需通过MAX_INT调整数字或使用无符号变量或任何东西。它只是：

HOWEVER, there's an alternative I stumbled upon that's even simpler, and I haven't yet figured out how it works. There's no need to adjust the numbers by MAX_INT or use unsigned variables or anything. It's simply:

avg = (low & high) + ((low ^ high) >> 1);

使用16位有符号整数的所有组合进行测试低和高在-32768..32767范围内，但尚未完全证实（无论如何我都是）。

Tested with all combinations of 16-bit signed integers low and high in the range -32768..32767, but not yet proven outright (by me anyway).

这篇关于安全整数中间值公式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！