Разъяснения решения для алгоритма

Question

я работаю над проблемой, которая выглядит следующим образом:

«Написать функцию, которая добавляет два номера Вы не должны использовать + или любые арифметические операторы..»

В базе 10, чтобы добавить два числа, вы можете разделить процесс сложения на два этапа:

1) Сложение без нести

2) Только перенесенное значений

Добавьте два вместе. Решение по существу делает это, но рекурсирует на значение 1) и значение 2), пока не будет больше перенесенных значений. Я не понимаю интуиции для этого - откуда мы знаем, что в конечном итоге переносимые значения будут равны нулю?

Ниже раствор:

int Add(int x, int y) 
{ 
    if (y == 0) 
     return x; 
    else 
     return Add(x^y, (x & y) << 1); 
} 

Answer 1

Если мы используем целочисленное представление с фиксированным числом битов (например, 32-битных целых чисел), то мы можем рассуждать следующим образом:

При любом данном вызове Add предположим, что y заканчивается на n нулевых битов. (Например, если двоичное представление y «ы заканчивается в 1000, то п равно 3.)

x & y Затем заканчивается в по крайней мере п нулевых бит, так как она будет иметь нулевую величину бит, где y делает.

И (x & y) << 1 заканчивается, по крайней мере, п   +   1 нулевыми битами, потому что он сдвигает все влево и добавляет нулевой бит до конца. (Исключение: если y == 0, то число нулевых бит «увеличившееся», и этот сдвиг является не оп Но в этом случае мы не достигли бы else в любом случае.).

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

---

Как это происходит, алгоритм остается правильным, даже если мы используем беззнаковое-целое представление, которое позволяет неограниченное число битов, но в этом случае это немного сложнее, чтобы показать. Ключевые наблюдения, что:

• приведенный выше аргумент, что каждый рекурсивный вызов увеличивает количество завершающих нулевых битов в оцененных y, по-прежнему имеет место. Поэтому, если yне в конечном итоге становится нулевым, то он должен расти без ограничений.
• Сумма x и y не изменяется от одного рекурсивного вызова к следующему; и x никогда не становится отрицательным (поскольку целочисленное представление даже не поддерживает это); так что y никогда не сможет превысить эту сумму.

Эти два факта, взятые вместе, показывают, что y должно со временем стать нулевым.