Сложность сложения без переноса

Question

Два двоичных числа могут быть представлены в обычном «обычном, избыточном» представлении (то есть ввести другую цифру, скажем, 2, чтобы получить неуникальное представление, такое, что любые два последовательных 2 имеют ноль между ними), так что сложениестановится свободным от переноскиЯ слышал, что сложность O (k), где k - длина более короткого из двух чисел.Но каков сам алгоритм?Кажется, он нигде не появляется в сети.Я знаю, что вы можете добавить 1 к такому представлению в постоянное время, чтобы результат сохранял регулярность.Но я не знаю, как это обобщить.

Answer 1

Я вижу, что это старый пост, и у автора здесь не так много недавней активности, но я все равно решил ответить.Как указал Ксан, дополнительный «алгоритм» показан на принципиальной схеме в этой статье .

Чтобы представить эту схему в виде традиционного уравнения, давайте сформулируем некоторые обозначения.Каждый «бит» в обозначении RBR фактически состоит из двух битов, поэтому для обозначения этих правого и левого битов я буду использовать [0] и [1] соответственно.Для ссылки на определенную позицию «бита» я буду использовать фигурные скобки {0}, {1}, {2}, ... {n}.

Добавление двух или трех отдельных битов может привести к двум-битная сумма (MSB традиционно называется битом переноса).На них также могут ссылаться [0] и [1], причем последний является битом переноса.Например:
(0+1+1)[0]=0, (0+1+1)[1]=1, (0+0+1)[0]=1, (0+0+1)[1]=0

Теперь без особых подробностей общий алгоритм добавления чисел z = x + y задается следующим образом:
z{n}[0] = ((x{n-1}[1] + x{n-1}[0] + y{n-1}[1])[0] + (y{n-1}[0]) + (x{n-2}[1] + x{n-2}[0] + y{n-2}[1])[1])[1]

z{n}[1] = ((x{n}[1] + x{n}[0] + y{n}[1])[0] + (y{n}[0]) + (x{n-1}[1] + x{n-1}[0] + y{n-1}[1])[1])[0]

Вы заметите, что здесь происходит некоторое перемещение, но алгоритм достигает O (n), потому что перенос ограничен двумя порядками.Также обратите внимание на особые соображения для z {0} и z {1}, которые определены на принципиальной схеме в вышеупомянутой ссылке.