2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Сравнение чисел без условных операторов
Сообщение19.01.2017, 01:23 
Заслуженный участник
Аватара пользователя


19/12/10
1546
mustitz в сообщении #1185778 писал(а):
К сожалению, это не работает, в случае Turbo C 1.5. Стандарт C, вообще говоря, не определяет размер типа int

Для 16-битных целых аналогично:
Используется синтаксис C
return (x | -x) >> 15;

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


05/09/12
2587
Либо я чего-то не понимаю....
Используется синтаксис C++
return 2-!(n^77);

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


04/06/13
82
_Ivana в сообщении #1185857 писал(а):
Либо я чего-то не понимаю....
Используется синтаксис C++
return 2-!(n^77);

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

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


19/12/10
1546
Генри Уоррен мл. "Алгоритмические трюки для программистов" в пункте 2.11 "Предикаты сравнения" рекомендует для предиката $x\ne y$ следующий код:
Используется синтаксис C
return ((x - y) | (y - x)) >> 31;

Тогда нужный код будет:
Используется синтаксис C
return a + (b - a) * (((n - 77) | (77 - n)) >> 31);

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


04/06/13
82
Разобрался с первой реализацией 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 выглядит не очень, поэтому я его не использовал тут, но если надо переделаю.

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


04/06/13
82
Используется синтаксис 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$.
Старший бит результата всегда будет установлен лишь в том случае, если мы будем учитывать и разницу вычитания большего из меньшего. Наверное, чтобы не выяснять кто больше, а кто меньше, мы просто делаем два раза вычитание, а потом применяем к результатам логическое ИЛИ, чтобы все установленные биты оказались в результате. Как-то так что-ли.

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


07/02/12
1403
Питер
mihaild в сообщении #1185633 писал(а):
"компилятор разберется"

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

-- 07.02.2017, 03:39 --
Знаковый сдвиг вниз на размерность числа заполняет все биты знаковым битом - обозвав результат маской, можно воспользоваться следующей конструкцией:
Код:
(a & mask) | (b & ~mask)
Знаковый бит в случае тождественного равенства можно заполнить по Уоррену (на практике почти не используется, т.к. почти везде есть аппаратное заполнения флагом нуля)
Код:
((x - y) | (y - x))
В случае неравенств просто разностью.
Код:
(x - y)
И тогда не надо ничего делить или умножать.

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

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

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



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

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


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

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