2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Сравнение чисел без условных операторов
Сообщение18.01.2017, 13:59 


04/06/13
82
Есть вот такое код:
Используется синтаксис Java
        int n = 77;
        int result;
        int a = 1;
        int b = 2;

        if (n == 77)
            result = a;
        else
            result = b;
 

Как можно переписать этот код без использование условных операторов, ухищрений с помощью циклов, map, используя лишь операции сложения, вычитания, умножения и деления, а тажке битовые операции?
В сети есть подобные задачи, но мне интересно как пришли к решению, а не готовое решение. Прошу направить в нужную сторону, потому что мыслей как это сделать с помощью арифметических операций нет.

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 14:13 
Аватара пользователя


08/08/14

991
Москва
Код:
result= n==77 ? A: b;

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 14:20 


04/06/13
82
Не, тернарный оператор - тоже ведь сравнение. :)

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 14:24 
Заслуженный участник
Аватара пользователя


16/07/14
8347
Цюрих
Gts в сообщении #1185623 писал(а):
как пришли к решению

0) работать с битовыми операциями я не умею, поэтому ограничимся арифметикой
1) отобразить любой конечный набор значений в любой другой можно легко, поэтому надо бы сделать что-то типа "$77$ в одно значение, все остальные - в другое"
2) скорее всего будет отделять положительные числа от нуля, поэтому сразу переведем $n$ в $(n - 77)^2$
3) если мы сможем получить функцию $f$ такую что $f(0) = a, f(x) = b, a \neq b$ при $x > 0$, то мы победили
4) из арифметики всё, кроме деления, не выводит за рамки многочленов - а они либо постоянны, либо принимают бесконечное множество значений; значит, нужно деление
5) надо что-то на что-то поделить, помня что деление происходит с отбрасыванием остатка, так, чтобы в $0$ получался один результат, а во всех положительных числах - другой
Ну и тут надо подумать, как ведут себя многочлены, и угадать.

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 14:28 


10/04/12
704
Ну... всё просто, любое сравнение даёт целое число 0 или 1, а далее строим выражение с учётом этого

Используется синтаксис C
int expression = (result == 77) * a + (result != 77) * b;
 


С практической точки зрения надо знать о существовании инструкции CMOV, поэтому достаточно ограничиваться простыми условиями типа

Используется синтаксис C
if (something) a = value;

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 14:37 
Заслуженный участник
Аватара пользователя


16/07/14
8347
Цюрих
С практической точки зрения надо писать условия и не выпендриваться, "компилятор разберется" (в таких случаях - точно).
Тут задача, как выразить одну функцию через другие. В данном случае ТС просил через арифметику и битовые операции.

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 15:10 


04/06/13
82
mustitz писал(а):
любое сравнение даёт целое число 0 или 1

Моя ошибка, что дополнительно в тексте не указал язык. Для Java такой номер не пройдёт, там результат сравнения является булевым типом, который не умножить на целочисленную переменную. Понадобится функция для преобразования boolean2int(). Это весьма смахивает на то, что предлагает mihaild:
mihaild писал(а):
отобразить любой конечный набор значений в любой другой можно легко, поэтому надо бы сделать что-то типа "$77$ в одно значение, все остальные - в другое"

Пока подумаю как конвертировать неотрицательное число в $1$, чтобы можно было умножать на $a$ или $b$. Тогда вместо сравнения
Используется синтаксис C
result == 77
, мы сделаем вычитание одного из другого или $XOR$, а нулевой результат будет нам говорить, что переменные равны и после инвертирования этот результат можно будет использовать в части
Используется синтаксис C
(result == 77) * a


mihaild, Ваш ответ пока разбираю, чтобы понять.

Практической пользы от этой задачи я не вижу. Вряд ли даже где надо экономить место (в микроконтроллерах) это понадобится.
Суть не в том, где это применить, а в красоте решения.

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 17:06 


04/06/13
82
Вот такой монстрик вышел:
код: [ скачать ] [ спрятать ]
Используется синтаксис Java
        byte n = 77;
        byte x;
        byte a = 1;
        byte b = 2;

/*
        if (n == 77)
            x = a;
        else
            x = b;
*/

        // Везде приходится делать приведение типов, потому что java по
        // умолчанию приводит всё к int. А с byte удобно работать, потому
        // что меньше кода для сдвигов.

        // Сделаем вычитание одного из другого. Нулевой результат
        // будет нам говорить, что переменные равны.
        byte buf = (byte)(n - 77);

        // Каждый установленный бит в числе говорит нам о том, что
        // число ненулевое. Поэтому мы каждый из возможно
        // установленных битов сдвинем, чтобы они оказались
        // в начале числа и логически сложим все эти значения.
        buf = (byte)(buf | (buf >> 8) | (buf >> 7) | (buf >> 6) | (buf >> 5)
            | (buf >> 4) | (buf >> 3) | (buf >> 2) | (buf >> 1));

        // Теперь мы выделим с помощью битовой маски этот первый бит.
        buf = (byte)(buf & 0x01);

        // Если нам надо выполнить условие if (n == 77) x = a, то
        // умножаем инвертированное значение buf на a.
        x = (byte)((~ buf & 0x01) * a + buf * b);

 

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 18:24 


10/04/12
704
А почему не так?
код: [ скачать ] [ спрятать ]
Используется синтаксис C
unsigned int is_not_zero(unsigned int x)
{
    unsigned int zero = 0;
    unsigned int ones = ~zero;
    unsigned int hi_one = (ones / 2) + 1;
    unsigned int t = (x & -x) * ones;
    return (t & hi_one) / hi_one;
}

unsigned int is_zero(unsigned int x)
{
    return 1 - is_not_zero(x);
}

int result = is_zero(x-77) * a + is_not_zero(x-77);
 


-- 18.01.2017, 17:43 --

Еще проще вариант

Используется синтаксис C
unsigned int is_not_equal(unsigned int x, unsigned int y)
{
    unsigned int zero = 0;
    unsigned int ones = ~zero;
    unsigned int hi_one = (ones / 2) + 1;
    return (((x-y) | (y-x)) & hi_one ) / hi_one ;
}


отсюда

Используется синтаксис C
unsigned int is_not_zero(unsigned in x)
{
    unsigned int zero = 0;
    unsigned int ones = ~zero;
    unsigned int hi_one = (ones / 2) + 1;
    return ((x | -x) & hi_one ) / hi_one ;
 
}

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 18:59 
Заслуженный участник
Аватара пользователя


16/07/14
8347
Цюрих
Так, тут надо точно определять, в какой области мы работаем и какие у нас есть операции:)
mustitz, например, использует конкретное битовое представление отрицательных чисел (и это кажется будет implementation defined).

Я делал отображение $0 \to a, \neq 0 \to b$ как $\frac{n^2 + 1}{n^2 + 2}$: $0$ переходит в $2$, остальное в $1$ (если только не возникает переполнения).

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 19:07 


10/04/12
704
mihaild,
У меня отрицательных чисел нет, везде беззнаковые целые. По стандарту С все операции определены, и проводяться по модулю $2^N$, UB не наблюдаеться.

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 19:41 
Заслуженный участник
Аватара пользователя


16/07/14
8347
Цюрих
mustitz да, правда. Я ведь даже пошел почитал, как определен унарный минус для беззнаковых, и всё равно написал чушь :?

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 20:15 
Заслуженный участник
Аватара пользователя


19/12/10
1546
mustitz в сообщении #1185680 писал(а):
Используется синтаксис C
unsigned int is_not_zero(unsigned in x)
{
    unsigned int zero = 0;
    unsigned int ones = ~zero;
    unsigned int hi_one = (ones / 2) + 1;
    return ((x | -x) & hi_one ) / hi_one ;
 
}

Из этого кода оставьте только последнюю строку, да и ту перепишите как:
Используется синтаксис C
return ((x | -x) & 0x80000000) >> 31;

UPD
И даже проще:
Используется синтаксис C
return (x | -x) >> 31;

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 21:02 


04/06/13
82
mustitz в сообщении #1185680 писал(а):
А почему не так?

Лишь потому, что не додумался. :)

 Профиль  
                  
 
 Re: Сравнение чисел без условных операторов
Сообщение18.01.2017, 23:16 


10/04/12
704
whitefox в сообщении #1185708 писал(а):
Из этого кода оставьте только последнюю строку, да и ту перепишите как:
Используется синтаксис C
return ((x | -x) & 0x80000000) >> 31;


К сожалению, это не работает, в случае Turbo C 1.5. Стандарт C, вообще говоря, не определяет размер типа int, поэтому предыдущие три строки по сути получают число, в котором все биты, кроме самого старшего, установлены в единицу, не закладываясь на размер unsigned int.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group