67. Add Binary

67. Add Binary

Difficulty: Easy

Topics: Math, String, Bit Manipulation, Simulation

Given two binary strings a and b, return their sum as a binary string.

Example 1:

• Input: a = "11", b = "1"
• Output: "100"

Example 2:

• Input: a = "1010", b = "1011"
• Output: "10101"

Constraints:

• 1 <= a.length, b.length <= 10⁴
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Solution:

We need to add two binary strings without converting them to integers (since they can be very long). The approach is similar to adding decimal numbers manually, but with base‑2.

Approach:

• Two‑pointer from the end: Start from the least significant bit (rightmost) of both strings, moving leftwards.
• Simulate binary addition: At each step, add the two corresponding bits plus any carry from the previous step. The resulting bit is sum % 2, and the new carry is intdiv($sum, 2) (floor division).
• Handle remaining digits and final carry: Continue the loop until both strings are exhausted and the carry becomes zero.
• Build result string: Prepend each new bit to the result string to avoid reversing at the end.

Let's implement this solution in PHP: 67. Add Binary

<?php
/**
 * @param String $a
 * @param String $b
 * @return String
 */
function addBinary(string $a, string $b): string
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo addBinary("11", "1") . "\n";               // "100"
echo addBinary("1010", "1011") . "\n";          // "10101"
?>

Explanation:

• Why not convert to integer? Binary strings can be up to 10⁴ characters long, which would overflow standard integer types.
• Adding step by step: By iterating from the end, we mimic how binary addition is performed manually. The $carry variable holds the overflow to the next higher bit.
• Handling different lengths: The loop continues as long as at least one string still has digits or there is a carry. Missing digits are treated as 0.
• Building the result: Appending to the front ($result = $bit . $result) ensures the most significant bit ends up on the left without an extra reverse operation.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub