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

Тема в разделе "C и С++ FAQ", создана пользователем NikSoft, 28 июн 2006.

Статус темы:
Закрыта.
  1. NikSoft

    NikSoft Гость

    Несколько месяцев назад мне было предложено решить следующую задачу на языке С.
    Необходимо найти минимум двух целых положительных 32-разрядных чисел, представленных в дополнительном коде. Программа не должна использовать операции сравнения и условных переходов, не должна использовать вспомогательные таблицы. Предложенное решение, приводимое ниже, включает 19 операций с учетом наличия возможности переполнения. Для отладки я использовал Visual Studio 2005, Project types: Visual C++, Win 32 Console Application
    Код (Text):
    #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 операций, игнорируя наличие возможности переполнения:
    Код (Text):
    (x+y-((signed)((((signed)(x-y))>>31)*(x-y)+(((signed)(y-x))>>31)*(y-x))))/2
    Следующий вопрос адресуется тем, кого заинтересовала эта задача. Существует ли решение с меньшим числом операций?
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей