Вступ

Додавання двійкових чисел є ключовою операцією в інформатиці і є важливим етапом для багатьох низькорівневих завдань. Хоча це може здаватися простим, програмування вимагає уваги до крайніх випадків, таких як нерівні довжини рядків і переноси.

Постановка задачі:

Нам задано два двійкових рядки, a та b. Завдання полягає в тому, щоб повернути їх суму у вигляді двійкового рядка.

Приклади:

1. Вхідні дані: a = "101", b = "11"
   Вихід: "1000"
   Пояснення: 101 (5 у десятковій системі) + 11 (3 у десятковій системі) = 1000 (8 у десятковій системі).
2. Вхідні дані: a = "110", b = "1"
   Вихід: "111"
   Пояснення: 110 (6 у десятковій системі) + 1 (1 у десятковій системі) = 111 (7 у десятковій системі).
3. Вхідні дані: a = "0", b = "0"
   Вихід: "0"

Обмеження:

• a та b — непорожні двійкові рядки (містять лише 0 та 1).
• Вхідні рядки можуть мати різну довжину.
• Вихід має бути дійсним двійковим рядком.

Огляд рішення:

Задачу можна розв’язати, симулюючи двійкове додавання, починаючи з найменш значущого біта (найправішого біта) і рухаючись до найстаршого біта (найлівішого біта). Перенос використовується для обробки випадків, коли сума двох бітів перевищує 1.

Підхід включає:

1. Забезпечення того, щоб обидва рядки мали однакову довжину, додаючи нулі до коротшого (концептуально, а не в коді).
2. Ітерація від найменш значущого біта до найстаршого.
3. Додавання відповідних бітів разом з будь-яким переносом з попереднього кроку.
4. Формування результату біт за бітом і управління переносом.

Реалізація на Ruby:

class AddBinary  
 def add_binary(a, b)  
 a, b = b, a if a.length < b.length  

 carry = 0  
 result = []  

 a_idx, b_idx = a.length - 1, b.length - 1  
 while a_idx >= 0 || carry > 0  
 sum = carry  
 sum += a[a_idx].to_i if a_idx >= 0  
 sum += b[b_idx].to_i if b_idx >= 0  

 result << (sum % 2)   
 carry = sum / 2   

 a_idx -= 1  
 b_idx -= 1  
 end  

 result.reverse.join  
 end  
end

Пояснення коду:

1. Забезпечення, щоб a була довшою:
   Якщо a коротша, ми міняємо їх місцями, щоб завжди обробляти довший рядок, що спрощує логіку.

2. Ініціалізація змінних:

• carry починається з 0, щоб зберігати перенос з попередніх додавань.
• result — масив для зберігання кожного отриманого двійкового біта (в зворотному порядку).

3. Ітерація від найменш значущого біта:
За допомогою a_idx і b_idx цикл обробляє біти від найправішого до найлівішого.

4. Додавання бітів і переносу:

• Для кожної позиції додаються перенос і відповідні біти з a і b (якщо вони є).
• Обчислюється результатуючий біт (sum % 2), і він додається до result.
• Оновлюється перенос для наступної ітерації (sum / 2).

5. Обробка залишкового переносу:
Якщо після завершення циклу залишився перенос, він буде доданий до результату.

6. Реверсування і з’єднання результату:
Оскільки біти обробляються від найменш значущого до найстаршого, масив результату має бути перевернутий, щоб сформувати кінцевий двійковий рядок.

Покрокове пояснення на прикладі:

Вхід: a = "101", b = "11"

1. Забезпечуємо, щоб a була довшою: Без змін (a = "101", b = "11").
2. Ініціалізація: carry = 0, result = [].
3. Ітерації:

• Перша ітерація:
  a[2] = 1, b[1] = 1, carry = 0.
  sum = 1 + 1 + 0 = 2.
  Додаємо 2 % 2 = 0 до result, оновлюємо carry = 2 / 2 = 1.
  result = [0].
• Друга ітерація:
  a[1] = 0, b[0] = 1, carry = 1.
  sum = 0 + 1 + 1 = 2.
  Додаємо 2 % 2 = 0 до result, оновлюємо carry = 2 / 2 = 1.
  result = [0, 0].
• Третя ітерація:
  a[0] = 1, b[-1] = nil, carry = 1.
  sum = 1 + 0 + 1 = 2.
  Додаємо 2 % 2 = 0 до result, оновлюємо carry = 2 / 2 = 1.
  result = [0, 0, 0].
• Четверта ітерація (залишковий перенос):
  sum = carry = 1.
  Додаємо 1 до result.
  result = [0, 0, 0, 1].
  Реверсування і з’єднання: "1000".

Ефективність:

• Часова складність: O(max⁡(n,m))O(\max(n, m)), де n та m — довжини рядків a та b, тому ми проходимо через довший рядок один раз.
• **Прmax(n, m)), для зберігання результату.

Висновок:

Ця реалізація ефективно обробляє додавання двійкових рядків, зберігаючи простоту. Подібно до задачі Two Sum, вона спирається на систематичний підхід для зменшення складності, вирішуючи задачу крок за кроком.

Перекладено з: Solving the Add Binary Problem in Ruby: A Step-by-Step Guide