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

Одна очень уважаемая компания просит желающих в ней работать решить перед собеседованием ряд задач. Вот одна из них.

            Дополнительный код это используемый в современных компьютерах способ кодирования целых чисел, при котором неотрицательное число X представляется «как есть» а отрицательное число X как ~(|X|-1). Таким образом, максимальное неотрицательное число, которое может быть представлено 32-мя разрядами дополнительного кода, есть 2³¹-1. Для любого неотрицательного числа в дополнительном коде старший разряд равен нулю, а для любого отрицательного — единице.

            Найдите метод поиска минимума из двух положительных 32-разрядных целых чисел представленных в дополнительном коде не использующий операций сравнения и условных переходов.

            Естественно интересен метод, использующий минимальное число операций и не использующий никаких вспомогательных таблиц. Вы можете пользоваться следующими 32-разрядными операциями:

            Известен способ нахождения минимума при помощи 4 операций, но конечно Вы можете дать ответ и в том случае если получили большее число операций.

#include <iostream.h>
#define	p(arg)	{cout << __FILE__ << ": " << __LINE__ << \
". " << #arg << " = <" << (arg) << ">" << "\n";};
unsigned  int  min (unsigned  int  x, unsigned  int  y)
{	signed  int  a = x - y;   // 1-я операция
	a >>= 31;                 // 2-я операция
	return  x & a | y &~ a;   // операции 3,4,5
};
main()
{	p(min(1, 2));
	p(min(2, 0));
	p(min(42, 659990));
	p(min(9999942, 659990));
	return  0;
};

Опубликовано: 2012.09.25, последняя правка: 2018.10.29    15:55

     2014/06/03 07:36, Алексей          # 

int min (int a, int b) {
   return (a + b - ABS (a - b))/2;
}

     2014/06/04 16:48, Автор сайта          # 

(a + b - (a - b) & 0x7FFFFFFF) / 2

     2016/03/28 20:02, rst256          # 

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su