Add Binary · Optimal Solution

Column addition, one bit at a time.

A hardware adder in every CPU performs binary addition exactly this way: start from the rightmost bit, add the two digits plus any carry from the previous column, record the result, and propagate the carry left. Given two binary strings, return their sum as a binary string. Walk both inputs from right to left, computing each column as (a + b + carry) mod 2 with carry (a + b + carry) / 2. O(n) time. O(n) space.

Interactive

Watch binary addition column by column

Concept

Three ideas behind binary addition

Every column follows the same rule. Carry is the only state that connects one column to the next.

right-to-left scan

Process columns from the least significant bit (rightmost) to the most significant. This mirrors how we add decimal numbers by hand — the carry can only flow left, never right.

carry propagation

When a column's sum reaches 2 or 3, the overflow carries into the next column as a 1. A single carry can cascade through many consecutive 1-bits — 1111 + 1 becomes 10000.

the result can grow

The sum may be one bit longer than the longer input. If carry survives past all input bits, it becomes a new leading 1. Without this final check the result would be silently truncated.

Algorithm

One loop, one carry register

Two pointers walk inward. A single integer tracks the carry.

  1. 1

    Initialize pointers and carry

    Set pointers at the rightmost positions of both strings. Set carry to 0.

  2. 2

    Process each column

    While either pointer is valid or carry is non-zero: extract each string's current bit (0 if that string is exhausted). Compute column sum = a-bit + b-bit + carry.

  3. 3

    Extract result bit and carry

    Result bit = sum % 2. New carry = sum / 2 (integer division). Prepend the result bit to the output.

  4. 4

    Advance pointers

    Decrement both pointers. If a pointer was already past the start of its string, its bit is treated as 0 in subsequent columns.

Edge Cases

Where carry changes everything

Most edge cases reduce to whether carry propagates, cascades, or creates a new bit.

Different lengths

The shorter string runs out first. Missing positions contribute 0, not an error. The loop continues as long as the longer string's pointer is valid or carry is non-zero.

Cascading carry

1111 + 1 produces a carry at every column. The single 1 ripples through all four 1-bits, flipping each to 0 and producing 10000 — one bit longer than the longer input.

Final carry bit

When both strings are exhausted but carry equals 1, a new leading bit must be emitted. The carry != 0 condition in the loop guard handles this — without it, the result would be silently truncated.