• Познакомьтесь с пентестом веб-приложений на практике в нашем новом бесплатном курсе

    «Анализ защищенности веб-приложений»

    🔥 Записаться бесплатно!

  • CTF с учебными материалами Codeby Games

    Обучение кибербезопасности в игровой форме. Более 200 заданий по Active Directory, OSINT, PWN, Веб, Стеганографии, Реверс-инжинирингу, Форензике и Криптографии. Школа CTF с бесплатными курсами по всем категориям.

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

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

NikSoft

Несколько месяцев назад мне было предложено решить следующую задачу на языке С.
Необходимо найти минимум двух целых положительных 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
Следующий вопрос адресуется тем, кого заинтересовала эта задача. Существует ли решение с меньшим числом операций?
 
C

communicay

Здесь приведено решение с 5 операциями:
 
Статус
Закрыто для дальнейших ответов.
Мы в соцсетях:

Обучение наступательной кибербезопасности в игровой форме. Начать игру!