安全整数中间值公式

Question

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

(low + high) / 2

用于二进制搜索。到目前为止，我一直使用“低+（高-低）/ 2”和“高-（高-低）/
2”来避免某些情况下的上溢和下溢，但不能同时使用这两种情况。现在，我正在寻找一种有效的方法来执行此操作，该方法适用于任何整数（假设整数范围为-
MAX_INT-1到MAX_INT）。

更新 ：结合詹德和彼得·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;

更新
：经进一步思考，即使您没有带符号的整数，这也将起作用。按位，有符号和无符号整数等效于加，减和布尔运算。因此，我们需要担心的是确保除法行为像无符号除法一样，我们可以通过使用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);

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