Избавиться от ветвления

Всем привет ) Возникла простая на первый взгляд задача, которую я не смог решить без использования ветвления с помощью одних лишь арифметических\логических операторов. Суть в следующем:
Если число не равно нулю, то оставить его как есть, иначе установить его в 1(а может и какое нибудь другое число). т.е.

Код (Text):

1. x = (x !=0) ? x : 1

Числа 32 бита, все стандартно. Решение нужно на ЯВУ, т.е. с использованием лишь логических и арифметических операций, без ассемблерохаков.
Есть идеи?

 

or eax,eax
setnz al
movzx eax,al

 

MSoft
А можно на ЯВУ с использованием >> << и т п? ) В java асм недоступен к сожалению ))

 

То что написано словами не совпадает с кодом:
"Если число не равно нулю, то установить его в 1, иначе оставить его как есть" не равно:

Код (Text):

1. x = (x != 0) ? x : 1

Используй инструкцию CMOVxx.

Код (Text):

1. MOV EAX, [X]
2. MOV EDX, 1      ; or any other value
3. TEST    EAX, EAX
4. CMOVZ   EAX, EDX        ; or use CMOVNZ

 

звиняюсь, перепутал. Еще раз, нужно математико-логическое решение на ЯВУ

 

С помощью только операций +, -, *, << и побитовых логических - математически невозможно: в первой же главе Уоррена доказывается, что так можно реализовать только такие функции, у которых k младших бит результата зависят только от k младших бит входов при любых k. У функции (x ? x : 1) младший бит результата зависит от всех бит x.
Если разрешать >> - то в принципе можно, например, так:

Код (Text):

1. y = x | x >> 16;
2. y = y | y >> 8;
3. y = y | y >> 4;
4. y = y | y >> 2;
5. y = y | y >> 1;
6. // теперь младший бит y равен OR от всех бит x, то есть 0, если x=0, и 1 иначе
7. x = x | (y & 1);

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

 

Некоторое время назад проскакивала подобная тема. Адаптированный под данную задачу вариант.

Код (Text):

1. nt n = 1;
2. int x = 7;
3. unsigned s = (x | -x)  >> (sizeof(x)*8 - 1);
4. int result = (s & x) + ((~s) & n);

 

Scratch,

Это же max(x, 1), суть тривиально.

 

>>Это же max(x, 1), суть тривиально.
А внутри max думаешь не ветвления?

 

Может мой вариант и не быстрее приведенных, зато выглядит симпатично.

Код (Text):

1. unsigned int a = THE_NUMBER;
2. a += (a-1)/-1;

 

Если на сях, то нет
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

 

Scratch

На C покатит?

Код (Text):

1. x = !!x;

upd. упс. Сорри. невнимательно прочитал условие.
Тогда:

Код (Text):

1. x = x + !x

 

Внутри приличных реализаций — нет. В случае с единицей это просто x+(x==0). На асме можно тупо cmp eax, 1 / adc eax, 0 сделать.

 

a = 3
a += (3-1)/-1 = 3 + 2/-1=1 fail. По условиж должно быть 3
r90
!x это ~x или оно возвращает 1 если x !=0?

 

Scratch
Нет там никакого fail. Если с устным счётом туговато, предлагаю скомпилировать.

 

l_inc либо это трололо либо ты не читал условия. a должно стать единицей только если оно ноль, а у тебя:

a += (a-1)/-1;
при a = 3 получаем
a += (3-1)/-1
то же самое, что
a += 2/-1
то же самое, что
a += -2
3+ (-2) = 1

 

Scratch
Вы компилировали? Что-то не верится.
Кстати, по условию в результате единица не только, если на входе нуль, а ещё и если на входе единица. Условия у меня выполнены. А у Вас проблемы с устным счётом. Конкретно вот здесь неверно:

P.S. Точнее неверно было ещё после первого преобразования, а в этом месте ошибка просто проявляется.

 

l_inc
У вас там всегда 1.

 

l_inc имел в виду

Код (Text):

1. int a = THE_NUMBER;
2. a += (unsigned)(a-1)/-1;

 

Scratch

!x == 1 если x != 0
Логические операторы C (!, &&, ||) возвращают 0 или 1.