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).