Нахождение максимума из двух чисел без условных операторов и операторов сравнения
Вы читаете свежую версию статьи. Мы актуализировали задачу, изначально опубликованную 02 февраля 2015 года.
112К открытий114К показов
Самый распространенный вариант реализации функции max — проверка знака выражения a - b
. В этом случае мы не можем использовать оператор сравнения, но можем использовать умножение.
Примечание Смысл задачи не в том, чтобы скрыть сравнение или условие в какую-нибудь стандартную функцию типа abs()
или стандартный оператор типа целочисленного деления, а в том, чтобы всё это сделать вообще без инструкций ветвления на уровне процессора.
Обозначим знак выражения a - b
как k
. Если a - b >= 0
, то k = 1
, иначе k = 0
. Пусть q
будет инвертированным значением k
.
Код будет иметь вид:
Это почти работоспособный код (можете проверить). Проблемы начинаются при переполнении. Предположим, что a = INT_MAX - 2
и b = -15
. В этом случае a - b
перестанет помещаться в INT_MAX
и вызовет переполнение (значение станет отрицательным).
Можно использовать тот же подход, но придумать другую реализацию. Нам нужно, чтобы выполнялось условие k = 1
, когда a > b
. Для этого придется использовать более сложную логику.
Когда возникает переполнение a - b
? Только тогда, когда a
положительное число, а b
отрицательное (или наоборот). Трудно обнаружить факт переполнения, но мы в состоянии понять, что a
и b
имеют разные знаки. Если у а
и b
разные знаки, то пусть k = sign(a)
.
Логика будет следующей:
1. если у a
и b
разные знаки:
// если a > 0
, то b < 0
и k = 1
.
// если a < 0
, то b > 0
и k = 0
.
// так или иначе, k = sign(a)
2. пусть k = sign(a)
3. иначе пусть k = sign(a - b)
// переполнение невозможно
Приведенный далее код реализует этот алгоритм, используя умножение вместо операторов сравнения (проверить):
Отметим, что для большей наглядности мы разделяем код на методы и вводим переменные. Это не самый компактный или эффективный способ написания кода, но так мы делаем код понятнее.
Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).
112К открытий114К показов