número entero Segura valor medio fórmula

Question

Busco a una fórmula eficiente de trabajo en Java que calcula la siguiente expresión:

(low + high)/2 

que se utiliza para la búsqueda binaria. Hasta ahora, he usado "bajo + (alto - bajo)/2" y "alto - (alto - bajo)/2" para evitar desbordamientos y subdesbordamientos en algunos casos, pero no en ambos. Ahora estoy buscando una manera eficiente de hacer esto, que sería para cualquier entero (asumiendo que los enteros van desde -MAX_INT - 1 a MAX_INT).

ACTUALIZACIÓN: La combinación de las respuestas de Jander y Peter G. y experimentando un tiempo me dio la siguiente fórmula para el elemento de valor del medio y sus vecinos inmediatos:

bajo-punto medio (igual a floor((low + high)/2), por ejemplo [ 2 3] -> 2, [2 4] -> 3, [-3 -2] -> -3)

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

más alta-punto medio (igual a ceil((low + high)/2), por ejemplo, [2 3] -> 3, [2 4] -> 3, [-3 -2] -> -2)

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

Antes del punto medio (igual a floor((low + high - 1)/2)), p. [2 3] -> 2, [2 4] -> 2, [-7 -3] -> -6)

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

Abierto punto medio (igual a ceil((low + high + 1)/2)), por ejemplo, [2 3] -> 3 , [2 4] -> 4, [-7 -3] -> -4)

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

o, sin bit a bit y (&) y o (|), el código ligeramente más lento (x >> 1 se puede sustituir por floor(x/2) para obtener fórmulas libres de operador en modo bit):

Extremo medio a la izquierda

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

Extremo derecho-punto medio

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

Antes-punto medio

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

Abierto punto medio

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

Nota: es considerado el >> operador anterior para ser firmado turno.

Answer 1

De http://aggregate.org/MAGIC/#Average%20of%20Integers:

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

es un promedio de desbordamiento a prueba de dos enteros sin signo.

Ahora, este truco solo funciona en enteros sin signo.Pero debido a ((a+x) + (b+x))/2 = (a+b)/2 + x, puede eludir la siguiente manera, si usted tiene enteros sin signo con el mismo tamaño de bits como sus enteros con signo:

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; 

---

ACTUALIZACIÓN: En un nuevo pensamiento, esto funcionará incluso si no tienen enteros con signo. Los enteros bit a bit, con signo y sin signo son equivalentes a las operaciones suma, resta y booleana. Entonces, todo lo que tenemos que preocuparnos es asegurarnos de que la división actúa como una división sin signo, lo que podemos hacer usando un cambio y enmascarando el bit más alto.

low += MAX+INT + 1; 
high += MAX_INT + 1; 
avg = (low & high) + (((low^high) >> 1) & MAX_INT); 
avg -= MAX_INT + 1; 

(Tenga en cuenta que si usted está usando Java, puede utilizar un desplazamiento sin signo, ... >>> 1, en lugar de (... >> 1) & MAX_INT.)

Sin embargo, hay una alternativa que me topé con eso es aún más simple, y Todavía no he descubierto cómo funciona. No es necesario ajustar los números en MAX_INT ni usar variables sin firmar ni nada. Es simplemente:

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

probado con todas las combinaciones de números enteros con signo de 16 bits y lowhigh en el rango -32768..32767, pero aún no se ha probado directamente (por mí).

Answer 2

Tenga en cuenta que ninguna de sus ideas funciona para low=-MAX_INT-1, high=MAX_INT. Lo mejor que puedo encontrar es algo así como low/2 + high/2 + ((low & 1) + (high & 1))/2.

Answer 3

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; 

Answer 4

Suponiendo high >= low, una variante de su enfoque inicial también debería funcionar, es decir:

low + ((high - low) >>> 1) 

donde >>> es un desplazamiento sin signo (como en Java).

La idea es que high - low nunca se desborda si el resultado se interpreta como un entero sin signo, por lo que el desplazamiento sin signo realiza correctamente la división entre 2 y la fórmula calcula el valor medio.