Виммельбух, 3, перетяжка
Виммельбух, 3, перетяжка
Виммельбух, 3, перетяжка

Нахождение максимума из двух чисел без условных операторов и операторов сравнения

Аватар Типичный программист
Отредактировано

Вы читаете свежую версию статьи. Мы актуализировали задачу, изначально опубликованную 02 февраля 2015 года.

112К открытий114К показов
Нахождение максимума из двух чисел без условных операторов и операторов сравнения

Самый распространенный вариант реализации функции max — проверка знака выражения a - b. В этом случае мы не можем использовать оператор сравнения, но можем использовать умножение.

Примечание Смысл задачи не в том, чтобы скрыть сравнение или условие в какую-нибудь стандартную функцию типа abs() или стандартный оператор типа целочисленного деления, а в том, чтобы всё это сделать вообще без инструкций ветвления на уровне процессора.

Обозначим знак выражения a - b как k. Если a - b >= 0, то k = 1, иначе k = 0. Пусть q будет инвертированным значением k.

Код будет иметь вид:

			/* Отражаем 1 в 0 и 0 в 1 */
int flip(int bit) {
	return 1^bit;
}

/* Возвращаем 1, если число положительное, и 0, если отрицательное*/
int sign(int a) {
	return flip((a >> (sizeof(int) * CHAR_BIT - 1)))) & 0x1);
}

int getMaxNaive(int a, int b) {
	int k = sign(a - b);
	int q = flip(k);
	return a * k + b * q;
}
		

Это почти работоспособный код (можете проверить). Проблемы начинаются при переполнении. Предположим, что 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) // переполнение невозможно

Приведенный далее код реализует этот алгоритм, используя умножение вместо операторов сравнения (проверить):

			int getMax(int a, int b) {
	int c = a - b;
	
	int sa = sign(a); // если a >= 0, то 1, иначе 0
	int sb = sign(b); // если a >= 1, то 1, иначе 0
	int sc = sign(c); // зависит от переполнения a - b
	
	/* Цель: найти k, которое = 1, если а > b, и 0, если a < b.
	 * если a = b, k не имеет значения */

	// Если у а и b равные знаки, то k = sign(a)
	int use_sign_of_a = sa ^ sb;
	
	// Если у a и b одинаковый знак, то k = sign(a - b)
	int use_sign_of_c = flip(sa ^ sb);
	
	int k = use_sign_of_a * sa + use_sign_of_c * sc;
	int q = flip(k); // отражение k

	return a * k + b * q;
}
		

Отметим, что для большей наглядности мы разделяем код на методы и вводим переменные. Это не самый компактный или эффективный способ написания кода, но так мы делаем код понятнее.

Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).

Следите за новыми постами
Следите за новыми постами по любимым темам
112К открытий114К показов