Binary Addition

You are tasked with implementing a function that adds two binary strings and returns their sum as a binary string. This is a fundamental operation often encountered in low-level programming, computer architecture, and digital logic design.

Problem Description

Given two non-empty binary strings, a and b, representing non-negative integers, compute their sum and return it as a binary string.

Key Requirements:

• The input strings a and b will only contain the characters '0' or '1'.
• The length of each input string will be between 1 and 10^4 (inclusive).
• Each string does not contain leading zeros, except for the number 0 itself.
• The output must also be a binary string.

Expected Behavior:

The function should simulate the manual process of binary addition, including handling carries.

Edge Cases to Consider:

• Strings of equal length.
• Strings of different lengths.
• Cases where a carry propagates beyond the most significant bit of the longer string.
• The sum resulting in "0".

Examples

Example 1:

Input: a = "11", b = "1"
Output: "100"
Explanation:
  11
+  1
----
 100

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"
Explanation:
  1010
+ 1011
------
 10101

Example 3:

Input: a = "0", b = "0"
Output: "0"
Explanation:
  0
+ 0
---
  0

Constraints

• 1 <= a.length, b.length <= 10^4
• a and b consist only of '0' or '1' characters.
• a and b do not have leading zeros (except for the number "0").
• Your algorithm should run efficiently, ideally with a time complexity proportional to the length of the longer string.

Notes

When performing binary addition, remember the following rules:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 0 with a carry of 1

You'll likely need to iterate through the strings from right to left (least significant bit to most significant bit), keeping track of any carry. A common approach is to process digits one by one, from the end of the strings, and then prepend the result to form the final binary string.