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

[whitefox]

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

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

Для 16-битных целых аналогично:

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

return (x | -x) >> 15;

[_Ivana]

Либо я чего-то не понимаю....

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

return 2-!(n^77);

[Gts]

_Ivana в сообщении #1185857 писал(а):

Либо я чего-то не понимаю....

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

return 2-!(n^77);

Основная суть такая же, как и у mustitz в плане того, что в Си/Си++ булевые выражения имеют представление в int.
Если у нас переменные захардкодены, то в этой точки зрения код интересен. :)

[whitefox]

Генри Уоррен мл. "Алгоритмические трюки для программистов" в пункте 2.11 "Предикаты сравнения" рекомендует для предиката $x\ne y$ следующий код:

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

return ((x - y) | (y - x)) >> 31;

Тогда нужный код будет:

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

return a + (b - a) * (((n - 77) | (77 - n)) >> 31);

[Gts]

Разобрался с первой реализацией is_not_zero().

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

Без бумажки с ручкой и комментариев, мне опыта не достаёт понимать Ваш код. :)

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

x & -x

На число наложим маску того же числа, только в дополнительном коде. Интересная конструкция. Мы так выделяем один бит для ненулевого числа.

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

t = (x & -x) * ones;

Тут мы число с выделенным битом умножаем на 0xFFFF (опустим для упрощения размеры int), что даёт нам 0xFFFF в случае ненулевого числа. Для нуля же будет нулевой результат.

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

(t & hi_one) / hi_one

Наложили маску 0x8000 (размерами int опять пренебрегли) и выделили старший бит в $t$. Если он установлен, то при делении на 0x8000 мы получим $1$, если сброшен, то $0$ (ведь деление целочисленное).

Иными словами, если входная переменная равна нулю, то на выходе мы получим нуль, иначе единицу.

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

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

Тут я, по простоте своей, делал бы инверсию результата от is_not_zero(), а потом бы снова маску применял. Ваше решение лучше.

Пошёл следующую функцию разбирать.

Вывод шестнадцатеричных чисел с помощью тега math выглядит не очень, поэтому я его не использовал тут, но если надо переделаю.

[Gts]

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

Смысл $((x - y) | (y - x))$ в том, что это выражение устанавливает биты результата, если входные числа разные.
Но процесс разработки этого выражения, постепенный ход мысли автора никак не дойдёт до меня.
Собственно, как можно понять что числа не равны? Можно вычесть из первого числа второе. Но этого будет недостаточно в нашем случае, потому что мы должны наложить маску hi_one для выделения старшего бита, который у нас может оказаться нулевым, при разных $x$ и $y$.
Старший бит результата всегда будет установлен лишь в том случае, если мы будем учитывать и разницу вычитания большего из меньшего. Наверное, чтобы не выяснять кто больше, а кто меньше, мы просто делаем два раза вычитание, а потом применяем к результатам логическое ИЛИ, чтобы все установленные биты оказались в результате. Как-то так что-ли.

[bondkim137]

mihaild в сообщении #1185633 писал(а):

"компилятор разберется"

Имел место быть относительно продолжительный период, когда в окне таргетированных устройств условные присвоения процессоры еще не умели, а предсказания переходов уже умели (если грубо). А компиляторы вообще мало чего хитрого умели. Потому, разбирая 'рандомную' (сложно предсказуемую) последовательность, все начинало очень тормозить на ошибках предсказаний процессора. С тех времен до сих пор во многих библиотеках мелькают #ifdef для базовых операций для процессоров с поддержкой условного присвоения в одну команду и без него, через логические workaround-ы.

-- 07.02.2017, 03:39 --
Знаковый сдвиг вниз на размерность числа заполняет все биты знаковым битом - обозвав результат маской, можно воспользоваться следующей конструкцией:

(a & mask) | (b & ~mask)

Знаковый бит в случае тождественного равенства можно заполнить по Уоррену (на практике почти не используется, т.к. почти везде есть аппаратное заполнения флагом нуля)

((x - y) | (y - x))

В случае неравенств просто разностью.

(x - y)

И тогда не надо ничего делить или умножать.

Но надо не забывать о переполнениях