Сравнение чисел без условных операторов

[Gts]

Есть вот такое код:

Используется синтаксис Java

        int n = 77;
        int result;
        int a = 1;
        int b = 2;

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

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

[levtsn]

result= n==77 ? A: b;

[Gts]

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

[mihaild]

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$ получался один результат, а во всех положительных числах - другой
Ну и тут надо подумать, как ведут себя многочлены, и угадать.

[mustitz]

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

Используется синтаксис C

int expression = (result == 77) * a + (result != 77) * b;
 

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

Используется синтаксис C

if (something) a = value;

[mihaild]

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

[Gts]

mustitz писал(а):

любое сравнение даёт целое число 0 или 1

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

mihaild писал(а):

отобразить любой конечный набор значений в любой другой можно легко, поэтому надо бы сделать что-то типа "$77$ в одно значение, все остальные - в другое"

Пока подумаю как конвертировать неотрицательное число в $1$, чтобы можно было умножать на $a$ или $b$. Тогда вместо сравнения

Используется синтаксис C

result == 77

, мы сделаем вычитание одного из другого или $XOR$, а нулевой результат будет нам говорить, что переменные равны и после инвертирования этот результат можно будет использовать в части

Используется синтаксис C

(result == 77) * a

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

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

[Gts]

Вот такой монстрик вышел:

Используется синтаксис 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);

 

[mustitz]

А почему не так?

Используется синтаксис 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 ;
  
}

[mihaild]

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

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

[mustitz]

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

[mihaild]

mustitz да, правда. Я ведь даже пошел почитал, как определен унарный минус для беззнаковых, и всё равно написал чушь

[whitefox]

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;

[Gts]

mustitz в сообщении #1185680 писал(а):

А почему не так?

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

[mustitz]

whitefox в сообщении #1185708 писал(а):

Из этого кода оставьте только последнюю строку, да и ту перепишите как:

Используется синтаксис C

return ((x | -x) & 0x80000000) >> 31;

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