Understanding Binary Arithmetic — Level 2: Implementation Guide

The Add Binary Algorithm

The classic "Add Binary" problem asks us to add two binary strings and return the result as a binary string. Here's the approach:

1. Start from the rightmost characters of both strings
2. Add corresponding digits along with any carry:
   • Convert each char to int (e.g., '1' → 1)
   • Sum = digit_a + digit_b + carry
3. Calculate the result digit: sum % 2 (0 or 1)
4. Calculate the new carry: sum // 2 (0 or 1)
5. Append result digit and continue
6. After the loop, reverse the result (we built it backwards)

Python Implementation

def addBinary(a: str, b: str) -> str:
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    result = []

    while i >= 0 or j >= 0 or carry:
        total = carry

        if i >= 0:
            total += int(a[i])  # Add digit from string a
            i -= 1

        if j >= 0:
            total += int(b[j])  # Add digit from string b
            j -= 1

        result.append(str(total % 2))  # Current bit
        carry = total // 2              # New carry

    return ''.join(reversed(result))

Key points:

• We build the result in reverse order, then reverse at the end
• The loop continues while there are digits OR a carry remaining
• Using a list and join() is more efficient than string concatenation

Java Implementation

public String addBinary(String a, String b) {
    StringBuilder result = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1;
    int carry = 0;

    while (i >= 0 || j >= 0 || carry > 0) {
        int total = carry;

        if (i >= 0) {
            total += a.charAt(i--) - '0';  // Convert char to int
        }

        if (j >= 0) {
            total += b.charAt(j--) - '0';
        }

        result.append(total % 2);
        carry = total / 2;
    }

    return result.reverse().toString();
}

Key points:

• charAt(i) - '0' converts char '0' or '1' to int 0 or 1
• StringBuilder is efficient for building strings
• reverse() method reverses in-place

C++ Implementation

string addBinary(string a, string b) {
    string result = "";
    int i = a.size() - 1, j = b.size() - 1;
    int carry = 0;

    while (i >= 0 || j >= 0 || carry) {
        int total = carry;

        if (i >= 0) {
            total += a[i--] - '0';
        }

        if (j >= 0) {
            total += b[j--] - '0';
        }

        result += to_string(total % 2);
        carry = total / 2;
    }

    reverse(result.begin(), result.end());
    return result;
}

Key points:

• Uses reverse() from the <algorithm> header
• to_string() converts int to string
• Same algorithm, different syntax

Understanding the Math

Why do total % 2 and total / 2 work? Let's trace through:

Pattern: The modulo operation gives us the current bit (even/odd), and integer division gives us the carry.

Common Pitfalls and Solutions

# BAD: Loop doesn't handle remaining carry
while i >= 0 or j >= 0:  # Missing "or carry"!

# BAD: Assumes both strings have same length
total += int(a[i]) + int(b[j])  # Crash if one is exhausted!

# BAD: Inefficient
result = ""
for bit in bits:
    result = bit + result  # Creates new string each time!

Alternative Approaches

1. Built-in Conversion (Python)

# Simple but limited by integer size
def addBinary(a, b):
    return bin(int(a, 2) + int(b, 2))[2:]

Warning: This fails for very long binary strings that exceed integer limits. The string-based approach handles arbitrarily long inputs.

2. Bit Manipulation

# Using XOR for sum, AND for carry
def addBinary(a, b):
    x, y = int(a, 2), int(b, 2)
    while y:
        x, y = x ^ y, (x & y) << 1
    return bin(x)[2:]

This uses bitwise operations: XOR adds without carry, AND finds carry positions, shift moves carry left.

Complexity Analysis