Program to add two binary numbers

An algorithm to add two binary numbers.

We will implement a simple algorithm in javascript to add two binary numbers and return its output in binary format. Everything will be written in ES6.

Example

Input:
'1010'
'1011'

Output:
10101

Learn more about binary addition here.

Implementation

  • We will use a temporary variable to store the carry from the addition.
  • Then we will sum the last digit from both the binary numbers and also add carry to it.
  • If the sum is greater than 1 then we will store the carry and use it again.
  • Repeat this for all the digits of the biggest number, If there is no digit in smaller number then use 0 instead.
  • In the end if the carry is not 0 then append it the result.
let addBinary = (a, b) => {
 
 let str = '';  //To store the final result
 let carry = 0; // To track the carry
 let aSize = a.length - 1;
 let bSize = b.length - 1;
 
 //Loop through both number while one of them has value
 while(aSize >= 0 || bSize >= 0){
       
  let tempA = a[aSize] || 0; // if value is present then use value else use 0
  let tempB = b[bSize] || 0; // if value is present then use value else use 0
  
  //Add the digits and carry
  let sum = Number(tempA) + Number(tempB) + carry;
  
  //if sum is greater than 1
  if(sum > 1){
    //Store the sum and carry
    sum = sum % 2;
    carry = 1;
  }else{
   //Else carry is zero
   carry = 0;
  }
  
  //store the result   
  str = sum + str;
        
  aSize--;
  bSize--;
}

//If carry still has value then append it to the result
if(carry){
  str = carry + str;
}
    
  return str;
};
Input:
console.log(addBinary('1010','1011'));

Output:
10101

sum = sum % 2 returns the exact value when addition is greater than 2. Like 1 + 1+ 1 = 3, so here sum is 1 and carry is also 1.

Time complexity: O(n) where n is the largest binary number.
Space complexity: O(1).

Time and Space complexity

  • We are looping till the biggest binary number still has value, so Time complexity is O(n) where n is the biggest binary number.
  • We are using constant space, so Space complexity is O(1).

Leave a Reply

Your email address will not be published. Required fields are marked *