Add Binary

Given two binary strings, return their sum as a binary string. Converting to integers directly can overflow for long inputs, so you must add digit-by-digit.

Why this is worth learning

A carry is the complete information one bit position needs from lower positions. Working from the right avoids converting an arbitrarily long input into a fixed-width integer.

Before coding: one-minute experiment

Add 111 and 1 by hand. What carry crosses each position, and why does the loop continue after both input indices are exhausted?

Function signature

func AddBinary(a, b string) string

Inputs / outputs

• a, b: binary strings (most significant bit first).
• Return: binary sum string.

Example

a = "1010", b = "1011"
Process from right:
0+1=1 (carry 0)
1+1=0 (carry 1)
0+0+1=1
1+1=0 (carry 1)
Final carry 1
Output: "10101"

Constraints

• 1 <= len(a), len(b) <= 10_000
• Strings contain only '0' and '1'

Core idea (near-solution)

Converting both strings to machine integers fails for inputs as long as 10,000 bits. A digit-by-digit calculation needs far less state: after a suffix has been resolved, its only effect on the next position is a carry of zero or one. Adding two available bits and that carry gives at most three, so quotient and remainder by two completely determine the next state regardless of input length.

Simulate binary addition from right to left with a carry.

Invariant: after processing suffixes a[i+1:] and b[j+1:], carry is the correct carry-out for that suffix.

Algorithm (step-by-step)

1. Set indices i=len(a)-1, j=len(b)-1, carry=0.
2. While i>=0 or j>=0 or carry>0:
   • Sum current bits plus carry.
   • Append sum % 2 to result.
   • Update carry = sum / 2.
   • Move indices left.
3. Reverse the result bytes and return as string.

Correctness sketch

After processing k low-order positions, the reversed output stores the correct low k bits of the sum, and carry is the quotient that must be added at the next position. Adding the two available input bits and carry produces a total from 0 to 3; remainder modulo 2 is the next result bit and quotient by 2 is the new carry. This preserves the invariant. The loop stops only after both inputs and carry are exhausted. Reversing the collected bits restores most-significant-first order without changing their values.

Trace (hand walkthrough)

Example input:
a = "1010", b = "1011"
Process from right:
0+1=1 (carry 0)
1+1=0 (carry 1)
0+0+1=1
1+1=0 (carry 1)
Final carry 1
Output: "10101"

Walk:
- from right: 0+1=1 (carry 0)
- 1+1=0 (carry 1)
- 0+0+1=1 (carry 0)
- 1+1=0 (carry 1), final carry 1 -> 10101

Pitfalls to avoid

• Forgetting to append the final carry.
• Building the result left-to-right without reversing.
• Mishandling different lengths.

Debugging lens

Test unequal lengths, a long carry chain, and all-zero strings. Do not trim leading zeroes silently: the existing implementation retains at least the maximum supplied input width.

Complexity

Time O(max(len(a),len(b))) and output/buffer space of the same order. Fixed-size carry and indices use O(1) additional state.

Implementation notes (Go)

• Build into a []byte and reverse at the end for efficiency.
• Use byte('0'+bit) when appending digits.

Contract precision

Inputs are nonempty binary strings. Output retains the maximum input width unless a carry adds one position; for example AddBinary("00","0") returns "00". This observable leading-zero convention is preserved.

Reconstruction checkpoint

Add 111 and 1 by hand. What carry crosses each position, and why does the loop continue after both input indices are exhausted?

Return to Bit Manipulation · Module quiz