Формула безопасного целого среднего значения

Question

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

(low + high) / 2

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

ОБНОВЛЕНИЕ : Объединение ответов от Джандераи Питер Г. и экспериментируя некоторое время, я получил следующие формулы для элемента среднего значения и его непосредственных соседей:

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

---

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

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

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

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

, где >>> - беззнаковое смещение (как в Java).

Идея состоит в том, что high - low никогда не переполняется, если результат интерпретируется как целое число без знака, поэтому сдвиг без знака правильно выполняет деление на 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

Обратите внимание, что ни одна из ваших идей не работает для low=-MAX_INT-1, high=MAX_INT.Лучшее, с чем я могу прийти, это что-то вроде low/2 + high/2 + ((low & 1) + (high & 1))/2.