Ассемблер - сложение через логические операции

[_Ivana]

Знакомил сегодня сына с системой команд процессора, и озадачил он меня следующим вопросом - можно ли реализовать операцию сложения через только логические операции, сдвиги и условные переходы? Без применения инкремента и декремента, естественно. Посидели, подумали с ним, придумали один вариант, который я только что протестировал и исправил одну ошибку. Интересно, как бы вы реализовали такую функцию? Наш код в спойлере оффтопа, написан на С, но это не принципиально - ассемблер на разных платформах порой сильно различается, но простейшие операции присутствуют и одинаковы на большинстве платформ.

(Оффтоп)

int SumLog(int a, int b)
{
   int c = a & b, d = a ^ b, e;
   while ( c ^ (e = c | ((c<<1) & d)) ) c = e;
   return (c<<1) ^ d;
}

PS почему-то при выборе синтаксиса языка в тексте кода отображаются не те символы. Вынужденно оформил через code.

[Joker_vD]

Как сложить два бита, $a$ и $b$? Результатом будут два бита, $s$ — бит суммы и $c$ — бит переноса, $a+b=2c+s$.

$$s=a\oplus b,\quad c=a\wedge b$$

Вопрос посложнее — у нас есть биты $a$ и $b$, бит входного переноса $c_i$, мы хотим получить биты суммы $s$ и выходного переноса $c_o$:

$$s=a\oplus b\oplus c_i,\quad c_o = (a\wedge( b \vee c_i))\vee (b\wedge c_i)$$

Теперь из таких одноразрядных сумматоров $(c_o,s)=S(a,b,c_i)$ можно собирать многоразрядные сумматоры $(c_o,\vec s)=S(\vec a, \vec b, c_i)$.

В конце-концов, все можно собрать из NAND-вентилей.

[Null]

Пока ($a\neq 0$) ($c=a \wedge b;b=a \oplus b; a=c\cdot 2;)
только долго

[_Ivana]

Спасибо, насколько я понял, Joker_vD кратко обрисовал первую часть главы 10 отсюда, а Null привел вполне рабочий алгоритм в несколько этапов из второй части. Долго - понятие растяжимое, максимум полтора десятки итераций имхо не долго.

У меня же получился почти такой же в идейном плане алгоритм, только я предварительно получаю в цикле целиком все слово битов переноса и только в конце применяю его для получения результата.

[Null]

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

У меня же получился почти такой же в идейном плане алгоритм, только я предварительно получаю в цикле целиком все слово битов переноса и только в конце применяю его для получения результата.

а после применения битов переноса новые переносы не возникнут?

[_Ivana]

Нет, потому что я получаю именно все слово переносов со всеми получившимися битами переноса во всех разрядах. Если не лениво, можете разобрать и/или проверить мой алгоритм, код я привел. Переменная $c$ после цикла является как раз этим полным словом всех переносов.

[venco]

Мне вариант Null нравится гораздо больше. У вас, _Ivana, зачем то различаются по смыслу переносы и слагаемые, хотя слово переносов - такое же слагаемое.

[_Ivana]

Мой вариант мы придумали с сыном навскидку, за десять минут, не зная существующих приведенных по ссылкам вариантов. И в процессе его придумывания исходили из четко декомпозированной задачи - сначала любым способом получаем полное слово переносов, а потом уже знаем что с ним делать. Фактически, сложность заключалась в получении этого слова переносов. А в алгоритме по ссылке (и у Null, насколько я понял, такой же или похожий, детально не разбирал) не было такой строгой декомпозиции и полное слово переноса не формировалось. Мне этот алгоритм тоже больше нравится, хотя не сказать что намного - цикл и там и там, количество операций в цикле примерно одинаково, условие выхода эквивалентно. А наш алгоритм получился таким из-за жесткости декомпозиции задачи.

ЗЫ сегодня думали как из положительного числа сделать отрицательное в дополнительном коде - для реализации вычитания по этой процедуре, ничего лучше чем инвертировать все биты и прибавить $1$ (по нашей неоптимальной процедуре сложения) не придумали.