Нахождение минимума двух чисел

  • Автор темы NikSoft
  • Дата начала
Статус
Закрыто для дальнейших ответов.
N

NikSoft

#1
Несколько месяцев назад мне было предложено решить следующую задачу на языке С.
Необходимо найти минимум двух целых положительных 32-разрядных чисел, представленных в дополнительном коде. Программа не должна использовать операции сравнения и условных переходов, не должна использовать вспомогательные таблицы. Предложенное решение, приводимое ниже, включает 19 операций с учетом наличия возможности переполнения. Для отладки я использовал Visual Studio 2005, Project types: Visual C++, Win 32 Console Application.

Код:
#include "stdafx.h"

int minxy(int x, int y )
{
int result;
result = (((signed)x)>>1)+(((signed)y)>>1)+((x&1)+(y&1))/2-(((signed)((((signed)(x-y))>>31)*(x-y)+(((signed)(y-x))>>31)*(y-x)))>>1);
return result; 
}

int _tmain(int argc, _TCHAR* argv[])
{
printf("%d, %d, min = %d\n", 5,1, minxy(5,1));
printf("%d, %d, min = %d\n", 5,5, minxy(5,5));
printf("%d, %d, min = %d\n", 4,17, minxy(4,17));
printf("%d, %d, min = %d\n", 100000 ,200000, minxy(100000, 200000));
printf("%x, %x, min = %x\n", 0x7fffffff , 1, minxy(0x7fffffff, 1));
printf("%x, %d, min = %d\n", 0x7fffffff , 100000, minxy(0x7fffffff, 100000));
printf("%x, %x, min = %x\n", 0x7fffffff , 0x7ffffffe, minxy(0x7fffffff, 0x7ffffffe));
printf("%x, %x, min = %x\n", 0x7fffffff , 0x7fffffff, minxy(0x7fffffff, 0x7fffffff));

return 0;
}
Предложенное решение включает 12 операций, игнорируя наличие возможности переполнения:
Код:
(x+y-((signed)((((signed)(x-y))>>31)*(x-y)+(((signed)(y-x))>>31)*(y-x))))/2
Следующий вопрос адресуется тем, кого заинтересовала эта задача. Существует ли решение с меньшим числом операций?
 
Статус
Закрыто для дальнейших ответов.