2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Ассемблер - сложение через логические операции
Сообщение02.01.2014, 02:17 


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

(Оффтоп)

Код:
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.

 Профиль  
                  
 
 Re: Ассемблер - сложение через логические операции
Сообщение02.01.2014, 05:40 
Заслуженный участник


09/09/10
3729
Как сложить два бита, $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-вентилей.

 Профиль  
                  
 
 Re: Ассемблер - сложение через логические операции
Сообщение02.01.2014, 09:54 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Ассемблер - сложение через логические операции
Сообщение02.01.2014, 16:51 


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

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

 Профиль  
                  
 
 Re: Ассемблер - сложение через логические операции
Сообщение02.01.2014, 16:59 
Заслуженный участник


12/08/10
1296
_Ivana в сообщении #808689 писал(а):
У меня же получился почти такой же в идейном плане алгоритм, только я предварительно получаю в цикле целиком все слово битов переноса и только в конце применяю его для получения результата.


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

 Профиль  
                  
 
 Re: Ассемблер - сложение через логические операции
Сообщение02.01.2014, 22:30 


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

 Профиль  
                  
 
 Re: Ассемблер - сложение через логические операции
Сообщение02.01.2014, 23:29 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Ассемблер - сложение через логические операции
Сообщение03.01.2014, 00:21 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

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



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

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


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

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