Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки 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/12/12 14:11 ••• Геннадий Тышов
Почему обречён язык Форт

2019/12/05 23:29 ••• Автор сайта
Слоны в комнате

2019/12/03 22:45 ••• Автор сайта
Следующие 7000 языков программирования: заключение

2019/12/03 22:36 ••• Автор сайта
Наблюдаемая эволюция языка программирования

2019/11/30 20:55 ••• Сергей
Каким должен быть язык программирования?

2019/11/09 21:27 ••• kt
Программирование без программистов — это медицина без врачей

2019/11/07 10:58 ••• kt
Признаки устаревшего языка

2019/10/28 23:55 ••• Автор сайта
Типы в инженерных задачах

2019/10/15 16:32 ••• kt
Модификация исполняемого кода как способ реализации массивов с изменяемыми границами

2019/10/07 14:15 ••• Автор сайта
О наименовании проекта и языка программирования

2019/09/19 15:23 ••• kt
Некошерный «goto»

2019/09/13 16:38 ••• Автор сайта
Программирование исчезнет. Будет дрессировка нейронных сетей