Add two binary strings

Last Updated : 24 Oct, 2024

Given two binary strings s1 and s2, the task is to return their sum.The input strings may contain leading zeros but the output string should not have any leading zeros.

Example:

Input: s1 = “1101”, s2 = “111”
Output: “10100”
Explanation:

Input: s1 = “00100”, s2 = “010”
Output: “110”

Bit-by-bit addition with carry – O(n + m) Time and O(1) Space

The idea is to first trim the leading zeros in the input strings. Now, start from the last characters of the strings and compute the digit sum one by one. If the sum becomes more than 1, then store carry for the next digits. Also consider this carry while calculating the digit sum. After calculating the sum, if an additional carry is generated, prepend a ‘1’ of the result.

C++

// C++ program to add two binary strings
// using Bit-by-Bit addition
#include <iostream>
using namespace std;

// Function to trim leading zeros from a binary string
string trimLeadingZeros(const string &s) {
    
    // Find the position of the first '1'
    size_t firstOne = s.find('1');
    return (firstOne == string::npos) ? "0" : s.substr(firstOne);
}

// This function adds two binary strings and return
// result as a third string
string addBinary(string &s1, string &s2) {
  
    // Trim leading zeros
    s1 = trimLeadingZeros(s1);
    s2 = trimLeadingZeros(s2);
  
    int n = s1.size();  
    int m = s2.size(); 
    
    // swap the strings if s1 is of smaller length
    if (n < m) {
        return addBinary(s2, s1);
    }
    
    int j = m - 1;  
    int carry = 0; 
    
    // Traverse both strings from the end
    for (int i = n - 1; i >= 0; i--) {
      
          // Current bit of s1
        int bit1 = s1[i] - '0';  
        int sum = bit1 + carry;
        
        // If there are remaining bits in s2, add them to the sum
        if (j >= 0) {
              
              // Current bit of s2
            int bit2 = s2[j] - '0';  
            sum += bit2;
            j--;
        }
        
        // Calculate the result bit and update carry
        int bit = sum % 2;
        carry = sum / 2;
        
        // Update the current bit in s1
        s1[i] = (char)(bit + '0');
    }
    
    // If there's any carry left, update s1
    if (carry > 0) {
        s1 = '1' + s1;
    }
    
    return s1;
}

int main() {
  
    string s1 = "1101", s2 = "111";
    cout << addBinary(s1, s2) << endl;
    return 0;
}

Java

// Java program to add two binary strings
// using Bit-by-Bit addition
class GfG {

    // Function to trim leading zeros from a binary string
    static String trimLeadingZeros(String s) {

        // Find the position of the first '1'
        int firstOne = s.indexOf('1');
        return (firstOne == -1) ? "0"
                                : s.substring(firstOne);
    }

    // This function adds two binary strings and return
    // result as a third string
    static String addBinary(String s1, String s2) {
      
        // Trim Leading Zeros
        s1 = trimLeadingZeros(s1);
        s2 = trimLeadingZeros(s2);
        
        int n = s1.length();
        int m = s2.length();

        // Swap the strings if s1 is of smaller length
        if (n < m) {
            return addBinary(s2, s1);
        }

        int j = m - 1;
        int carry = 0;
        StringBuilder result = new StringBuilder();

        // Traverse both strings from the end
        for (int i = n - 1; i >= 0; i--) {

            // Current bit of s1
            int bit1 = s1.charAt(i) - '0';
            int sum = bit1 + carry;

            // If there are remaining bits in s2, add them
            // to the sum
            if (j >= 0) {

                // Current bit of s2
                int bit2 = s2.charAt(j) - '0';
                sum += bit2;
                j--;
            }

            // Calculate the result bit and update carry
            int bit = sum % 2;
            carry = sum / 2;

            // Update the current bit in result
            result.append((char)(bit + '0'));
        }

        // If there's any carry left, update the result
        if (carry > 0)
            result.append('1');

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

    public static void main(String[] args) {
        String s1 = "1101";
        String s2 = "111";

        System.out.println(addBinary(s1, s2));
    }
}

Python3

# Python program to add two binary strings
# using Bit-by-Bit addition

def trimLeadingZeros(s):
    
    # Find the position of the first '1'
    firstOne = s.find('1')
    return s[firstOne:] if firstOne != -1 else "0"


# This function adds two binary strings and return
# result as a third string
def addBinary(s1, s2):
    
    # Trim Leading Zeros
    s1 = trimLeadingZeros(s1)
    s2 = trimLeadingZeros(s2)
    
    n = len(s1)
    m = len(s2)

    # Swap the strings if s1 is of smaller length
    if n < m:
        s1, s2 = s2, s1
        n, m = m, n

    j = m - 1
    carry = 0
    result = []

    # Traverse both strings from the end
    for i in range(n - 1, -1, -1):

        # Current bit of s1
        bit1 = int(s1[i])
        bitSum = bit1 + carry

        # If there are remaining bits in s2
        # add them to the bitSum
        if j >= 0:
            # Current bit of s2
            bit2 = int(s2[j])
            bitSum += bit2
            j -= 1

        # Calculate the result bit and update carry
        bit = bitSum % 2
        carry = bitSum // 2

        # Update the current bit in result
        result.append(str(bit))

    # If there's any carry left, prepend it to the result
    if carry > 0:
        result.append('1')

    return ''.join(result[::-1])


if __name__ == "__main__":
    s1 = "1101"
    s2 = "111"
    print(addBinary(s1, s2))

// C# program to add two binary strings
// using Bit-by-Bit addition

using System;

class GfG {
  
    // Function to trim leading zeros from a binary string
    static string trimLeadingZeros(string s) {

        // Find the position of the first '1'
        int firstOne = s.IndexOf('1');
        return (firstOne == -1) ? "0" : s.Substring(firstOne);
    }

  
    // This function adds two binary strings and return
    // result as a third string
    static string addBinary(string s1, string s2) {
        
        // Trim leading zeros
        s1 = trimLeadingZeros(s1);
        s2 = trimLeadingZeros(s2);
      
        int n = s1.Length;
        int m = s2.Length;

        // Swap the strings if s1 is of smaller length
        if (n < m) {
            return addBinary(s2, s1);
        }

        int j = m - 1;
        int carry = 0;
        char[] result = new char[n];

        // Traverse both strings from the end
        for (int i = n - 1; i >= 0; i--) {

            // Current bit of s1
            int bit1 = s1[i] - '0';
            int sum = bit1 + carry;

            // If there are remaining bits in s2, add them to the sum
            if (j >= 0) {
              
                // Current bit of s2
                int bit2 = s2[j] - '0';
                sum += bit2;
                j--;
            }

            // Calculate the result bit and update carry
            int bit = sum % 2;
            carry = sum / 2;

            // Update the current bit in result
            result[i] = (char)(bit + '0');
        }

        // If there's any carry left, prepend it to the result
        if (carry > 0) {
            return '1' + new string(result);
        }

        return new string(result);
    }

    static void Main() {
        string s1 = "1101";
        string s2 = "111";
        Console.WriteLine(addBinary(s1, s2));
    }
}

JavaScript

// JavaScript program to add two binary strings
// using Bit-by-Bit addition

// Function to trim leading zeros from a binary string
function trimLeadingZeros(s) {
    
    // Find the position of the first '1'
    let firstOne = s.indexOf('1');
    return (firstOne === -1) ? "0" : s.substring(firstOne);
}

// This function adds two binary strings and return
// result as a third string
function addBinary(s1, s2) {
    
    // Trim leading zeros
    s1 = trimLeadingZeros(s1);
    s2 = trimLeadingZeros(s2);

    let n = s1.length;
    let m = s2.length;

    // Swap the strings if s1 is of smaller length
    if (n < m) {
        return addBinary(s2, s1);
    }

    let j = m - 1;
    let carry = 0;
    let result = [];

    // Traverse both strings from the end
    for (let i = n - 1; i >= 0; i--) {

        // Current bit of s1
        let bit1 = s1[i] - '0';
        let sum = bit1 + carry;

        // If there are remaining bits in s2, add them to the sum
        if (j >= 0) {
            // Current bit of s2
            let bit2 = s2[j] - '0';
            sum += bit2;
            j--;
        }

        // Calculate the result bit and update carry
        let bit = sum % 2;
        carry = Math.floor(sum / 2);

        // Update the current bit in result
        result.push(bit);
    }

    // If there's any carry left, prepend it to the result
    if (carry > 0) {
        result.push(1);
    }

    return result.reverse().join('');
}

console.log(addBinary("1101", "111"));

Output

Time Complexity: O(n + m), for traversing the strings.
Auxiliary Space: O(n), for result array as strings are immutable in most of language and O(1) in C++ where strings are mutable.

Related Articles: