Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки 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;
};

Последняя правка: 2014-12-04    12:59

ОценитеОценки посетителей
   █████████████████████ 5 (50%)
   █████ 1 (10%)
   █████ 1 (10%)
   █████████████ 3 (30%)

Отзывы

     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++.

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

2018/04/16 15:09, Олег
Русский язык и программирование

2018/04/02 22:42, rst256
Программирование без программистов — это медицина без врачей

2018/03/25 21:14, Денис Будяк
Энтузиасты-разработчики компиляторов и их проекты

2018/03/21 23:37, Marat
Почему обречён язык Форт

2018/03/10 20:05, Comdiv
«Двухмерный» синтаксис Python

2018/02/24 14:51, Эникейщик
Русской операционной системой должна стать ReactOS

2017/12/12 13:32, Comdiv
Отечественные разработки

2017/11/05 17:26, rst256
Электроника без электронщиков