Add Binary - Implementation

Here is the complete solution:

function addBinary(a, b)
    result := ""
    carry := 0
    i := length of a - 1
    j := length of b - 1
    while i ≥ 0 or j ≥ 0 or carry > 0
        sum := carry
        if i ≥ 0 then
            sum := sum + (a[i] - '0')
            i := i - 1
        if j ≥ 0 then
            sum := sum + (b[j] - '0')
            j := j - 1
        result := (sum mod 2) + result    // Prepend digit
        carry := sum / 2                  // Integer division
    return result

Time: $O(\max(n, m))$ where $n$ and $m$ are the lengths of $a$ and $b$. Space: $O(\max(n, m))$ for the result string. This pattern works for adding numbers in any base.