#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/number-bases/add-binary-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/number-bases/add-binary-implementation

Repovive

Add Binary - Implementation - Number Bases | Math Fundamentals | Repovive

Repovive.

Math Fundamentals18 sections · 842 units13h total

Open in Course

Add Binary - Implementation

Pseudocode solution

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.