Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

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

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

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

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

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

Мнемоника Эквивалентная
операция языка Си
Комментарий
add(x, y) x + y сложение в дополнительном коде
sub(x, y) x - y вычитание в дополнительном коде
mul(x, y) x * y умножение в дополнительном коде
sdiv(x, y) ((signed)x) / ((signed)y) знаковое деление в дополнительном коде
udiv(x, y) ((unsigned)x) / ((unsigned)y) беззнаковое деление в дополнительном коде
or(x, y),
xor(x, y),
and(x, y)
x | y
x ^ y
x & y
логические операции
orn(x, y),
xorn(x, y),
andn(x, y)
x | ~y
x ^ ~y
x & ~y
логические операции с инверсией второго аргумента
shl(x, y) x << y сдвиг влево
shra(x, y) ((signed)x) >> y арифметический сдвиг вправо (с распространением знакового разряда)
shrl(x, y) ((unsigned)x) >> y логический сдвиг вправо (с распространением нуля)

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

            Интересная задача. Ниже в рамке приведено её решение 5 операциями на Си (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

ОценитеОценки посетителей
   ████████████████████ 7 (46.6%)
   ███ 1 (6.66%)
   ███ 1 (6.66%)
   █████████████████ 6 (40%)

Отзывы

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

Не совсем то, но вот ещё решение:
int min (int a, int b) {
  return (a + b - ABS (a - b))/2;
}

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

Операции ABS нет в перечне «позволенного». Но её можно заменить на AND:

(a + b - (a - b) & 0x7FFFFFFF) / 2
Итого 5 операций: «-», «&», «+», «-», «/».

     2016/03/28 20:02, rst256          # 

Только зря он в этом решении декларирует аргументы у функции min как без знаковые. Правильнее было бы как со знаком, ведь работать этот код верно будет только как раз для чисел со знаком. А потом ещё говорят, что си небезопасный язык.

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

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

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Новости и прочее

Политика размещения комментариев и статей

Предложения и замечания

Все голосования

Компьютерные ребусы и этюды для программистов

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

Утилита транслитерации русского C/C++ в стандартный

Решение системы уравнений методом Гаусса. Программа на русском C++.

Последние комментарии

2019/06/25 11:22 ••• VIT1972
Идеальный транслятор

2019/06/05 23:21 ••• kt
К вопросу о совершенствовании языка программирования

2019/06/04 14:52 ••• Неслучайный читатель
Деньги = работа / знание

2019/05/29 00:42 ••• rst256
Программирование без программистов — это медицина без врачей

2019/05/14 16:10 ••• utkin
Обработка ошибок

2019/05/09 18:05 ••• евгений
Русский язык и программирование

2019/04/28 14:08 ••• Автор сайта
Статьи Дмитрия Караваева

2019/04/22 16:19 ••• Автор сайта
Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

2019/04/03 22:24 ••• Антон
Все голосования

2019/04/02 12:28 ••• Автор сайта
Шестнадцатиричные и двоичные константы

2019/04/02 12:25 ••• Автор сайта
Выбор кодировки для компилятора

2019/03/24 14:55 ••• Автор сайта
Реализация двухстековой модели размещения данных