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: