Safe целых среднего значения формула

Question

Ищем эффективную формулу, работающей в Java, которая вычисляет следующее выражение:

(low + high)/2 

, который используется для бинарного поиска. До сих пор я использовал «low + (high-low)/2» и «high - (high-low)/2» , чтобы избежать переполнения и недоиспользования в некоторых случаях, но не обоих. Теперь я ищу эффективный способ сделать это, что бы для любого целого числа (предполагая, что целые числа варьируются от -MAX_INT-1 до MAX_INT).

UPDATE: Объединяя ответы от Jander и Питера Г. и экспериментирования некоторое время я получил следующие формулы для среднего значения элемента и его ближайшие соседи:

Самая низкая-средняя точка (равные 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); 

After-середины

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; 

---

UPDATE: О дальнейшей мысли, что это будет работать, даже если вы не имеют целых чисел со знаком. Побитовые, подписанные и беззнаковые целые числа эквивалентны над сложениями, вычитанием и булевыми операциями. Итак, все, о чем нам нужно беспокоиться, - это убедиться, что деление действует как беззнаковое разделение, которое мы можем сделать, используя сдвиг и маскируя самый верхний бит.

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, но еще не доказано прямое (от меня в любом случае).

Answer 2

Обратите внимание, что ни одна из ваших идей не работает для low=-MAX_INT-1, high=MAX_INT. Лучшее, что я мог найти, это что-то вроде 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

Предполагая high >= low, вариант вашего первоначального подхода должен также работать, то есть:

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

где >>> это беззнаковый сдвиг (как в Java).

Идея состоит в том, что high - low никогда не переполняется, если результат интерпретируется как целое без знака, поэтому сдвиг без знака выполняет деление на 2, а формула вычисляет среднее значение.