Беседы о программировании 020 :: Функции min(a,b) и max(a,b) для чисел без знака


Здесь рассматриваются функции определения минимума и максимума из двух чисел без знака. Данная статья — прямое продолжение статьи про эти же функции со знаком. Поэтому если вы её не читали, то лучше прочитать, так как здесь показана лишь разница метода 4 для знаковых и беззнаковых чисел, а также сводная таблица сравнения для всех вместе.

Для тех, кто прочитал предыдущую статью, сделаю краткое пояснение к этой.

  • Все функции с номерами от 0 до 3, которые там были, остаются без изменений, разве что нужно поменять i32 на u32 убедиться, что операции вроде -(a>=b) работают корректно (дают либо 0, либо -1). То есть, если нужно, привести промежуточные вычисления к типу i32. Сами же алгоритмы остаются прежними.
  • Функции с номерами 5 и 6 удалены из рассмотрения.
  • Функция 0 разбита на 2 части: a и b, первая является копией аналогичной функции 0 из предыдущей статьи, а вторая — её исправленная версия, в которой «больше» заменено на «меньше» и наоборот (кто помнит эпичный эксперимент, тот понял).

Вся алгоритмическая разница находится только в функции doz4, которую и рассмотрим.

Метод 4

Напомню, что это единственный метод, не содержащий ветвлений в коде программы и работающий для абсолютно всех возможных входных данных.

Формула после return имеет вот такой вид:

doz4u

Обратите внимание, что сдвиг знаковый! В коде программы даже присутствует приведение к i32 для этого. Поясним данную формулу.

В квадратных скобках в процессе всех вычислений нас будет интересовать только старший значащий бит, который символизирует значение 231. Когда мы интерпретируем число как знаковое, знаковый сдвиг даст нам либо 0, либо -1, которое и вступит в решающее побитового И с числом d.

В больших круглых скобках у нас побитовое ИЛИ,  слева от которого ~a&b, справа ~(a^b)&d. Отсюда сразу получаем первый случай.

Первый случай. Числа a и b имеют одинаковое значение старшего бита. То есть либо a>=231 И b>=231, либо a<231 И b<231. Выражение ~a&b всегда будет давать ноль в старшем бите, а ~(a^b) — единицу. Таким образом, судьба всей круглой скобки, которая сдвигается вправо, зависит от старшего бита числа d. Есть два варианта.

  1. d<231. Это значит, что при вычитании не было заёма, то есть a>=b. В этом случае после всех манипуляций значение квадратной скобки будет равно 0, а после отрицания — -1, и итоговый ответ будет равен d.
  2. d>=231. Такое может быть только при возникновении заёма, а значит a<b. В квадратных скобках получим -1, после отрицания — 0, и формула даст 0.

Второй случай. Переменные a и b имеют разные значения старшего значащего бита. Выражение ~(a^b) всегда будет давать ноль в старшем бите, поэтому вся судьба квадратной скобки определяется выражением ~a&b. Оно даст ноль только в случае a>=231 И b<231, то есть когда a>b, и единицу в противном случае. Таким образом, в первом случае получим в квадратных скобках ноль (а после отрицания -1), а во втором -1 (а после отрицания 0), что и требуется.

Метод зависит от знакового сдвига, поэтому в ряде случаев (когда процессор или язык не поддерживают знаковый сдвиг) придётся заменять знаковый сдвиг на беззнаковый с отрицанием.

Сравнение скорости

Процессор Core 2 Duo E8400 @ 3ГГц. Компилятор VС++ 2015. Время указано в секундах. Для измерения времени через наши функции прогонялось 232 пар чисел.

В таблицу включены результаты из предыдущей статьи.

min_max_u_comp

Напомню, что методы 0a и 0b — исходный и «исправленный» варианты обычной функции с ветвлением из предыдущей статьи.

Изучить данную таблицу вы можете самостоятельно. Интересным для меня здесь является только то, что некоторые беззнаковые функции работают сильно медленнее аналогичных знаковых.

Вывод

Для функция взятия минимума и максимума с огромным отрывом побеждает обычный классический алгоритм с ветвлением. Конечно, мы помним, что для архитектуры x86 такой код ветвлений не содержит, поэтому на каких-то других машинах ситуация может стать обратной. Но это повод для другого исследования.