Javascript: Add two binary numbers (returning binary)

Question

I have two inputs in binary, and I'm returning the addition result in binary as well.

var addBinary = function(a, b) {
    var dec = Number(parseInt(a, 2)) + Number(parseInt(b, 2));
    return dec.toString(2);
};

For some insanely big binary like

a = 10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101

b = 110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011

I'm outputting

110111101100010011000101110110100000011101000101011000000000000000000000000000000000000000000000000

where the supposed correct output is

110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000

Is it because of overflow? If so, what are the restrictions in Javascript for binary addition overflow? Sorry for the bunch of 1's and 0's.

Inflated

Javascript is limited to 53 bits thus the overflow action. This question might have the answers for you #30678803 – Valonia

You don't need those Number calls. parseInt already returns numbers. – Raddie

Answer 1

I've developed a solution for binary addition in Javascript.

My initial goal was to solidify my understanding of binary logic by replicating the mechanisms used in digital binary adder circuits in Javascript (no base conversions or bitwise operators used).

You can find a working version of my original project on CodePen.

It's doing a lot more with the DOM than you probably need, but when I plugged in your numbers (with tweaks mentioned below), I was happy to see that it worked!

Working Solution Code << this project is modified from my original project and contains only the code needed to output the correct answer.

This solution assumes that a and b are strings of the same length. To use this solution your input variables should be modified to:

var a = "000010100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"

var b = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"

(I just filled in the missing digits at the front of var a with zeros.)

As you can see, I recreated all of the components used in a physical implementation of a binary adder circuit:

Half Adder:

function halfAdder(a, b){
  const sum = xor(a,b);
  const carry = and(a,b);
  return [sum, carry];
}

Full Adder:

function fullAdder(a, b, carry){
  halfAdd = halfAdder(a,b);
  const sum = xor(carry, halfAdd[0]);
  carry = and(carry, halfAdd[0]);
  carry = or(carry, halfAdd[1]);
  return [sum, carry];
}

Logic Gates:

function xor(a, b){return (a === b ? 0 : 1);}
function and(a, b){return a == 1 && b == 1 ? 1 : 0;}
function or(a, b){return (a || b);}

Main Function:

function addBinary(a, b){

  let sum = '';
  let carry = '';

  for(var i = a.length-1;i>=0; i--){
    if(i == a.length-1){
      //half add the first pair
      const halfAdd1 = halfAdder(a[i],b[i]);
      sum = halfAdd1[0]+sum;
      carry = halfAdd1[1];
    }else{
      //full add the rest
      const fullAdd = fullAdder(a[i],b[i],carry);
      sum = fullAdd[0]+sum;
      carry = fullAdd[1];
    }
  }

  return carry ? carry + sum : sum;
}

So then, addBinary(a,b) produces the correct answer!

var a = "000010100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
var b = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"
var answer = "110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000";

console.log(addBinary(a, b) == answer); //true

I hope some of what I've done here can be useful to you too!

Franzoni

nice! I iterated on this and added support for binary strings of different lengths :-) https://mcmap.net/q/555696/-javascript-add-two-binary-numbers-returning-binary – Corduroys

Nice! Have you compared the time and space complexity with the built in JS adder? – Mellott

Answer 2

Here's my take on this:

The logic is simple, just like taught in elementary school, starting from the right-most digit: I add the first number's last digit and and second number's last digit, and keep the carry for next round.

On each round (inside the while) I right-trim both numbers, so for example:

// number
1101 -> 110
// The math is simple: 1101/10|0 (divide by 10 and convert to integer)

Inputs & output are Strings to overcome JS maximum integer limitations, where a String's length can be much larger.

Full code:

function binaryAddition(a,b){
  var result = "",
      carry = 0

  while(a || b || carry){
    let sum = +a.slice(-1) + +b.slice(-1) + carry // get last digit from each number and sum 

    if( sum > 1 ){  
      result = sum%2 + result
      carry = 1
    }
    else{
      result = sum + result
      carry = 0
    }
    
    // trim last digit (110 -> 11)
    a = a.slice(0, -1)
    b = b.slice(0, -1)
  }
  
  return result
}

// Tests
[
  ["0","0"],
  ["1","1"],
  ["1","0"],
  ["0","1"],
  ["10","1"],
  ["11","1"],
  ["10","10"],
  ["111","111"],
  ["1010","11"]
].forEach(numbers => 
   document.write(
     numbers[0] + " + " + 
     numbers[1] + " = " + 
     binaryAddition(numbers[0], numbers[1]) + 
     "      <mark> (" +
     parseInt(numbers[0], 2) + " + " + 
     parseInt(numbers[1], 2) + " = " + 
     parseInt(binaryAddition(numbers[0], numbers[1]),2) +
     ")</mark><br>" 
   )
)
document.body.style="font:16px monospace";

Inveterate

Can you explain what the plus sign in front of a.slice(-1) does here? – Cordwain

@DanielWilliams - it's a "trick" for converting String to Number (integer). javascript will evaluate the expression as a number if a mathematical operation is applied before a String – Inveterate

Answer 3

Inspired by @thepatriot, I created a one-liner version using the BigInt object.

var addBinary = (a, b) => {
  return (BigInt(`0b${a}`) + BigInt(`0b${b}`)).toString(2);
};

console.log(addBinary('10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101','110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011'));

Calipash

Answer 4

Forget about Javascript's precision of operating, think about how to plus one binary in math.

For example, 11 + 10.

First, we should start from right to left. Now we get 1 + 0 = 1 After that, we move to next. 1 + 1 = 10 If we use Javascript, how to get the result.

We know that, Mod can get the rest number, Division can get the carry. In the decimal system, we get 1 + 1 = 2, how to transfer 2 to 10. We can use

result % 2   // we can get single digit
result / 2 | 0   // we can get tens digit, `| 0` can remove decimal.

Now we can just concat the two strings together.

BinaryNumber = result / 2 | 0 + result % 2 + ''  // string concat

So our final code can be this:

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    var i = a.length - 1;
    var j = b.length - 1;
    var carry = 0;
    var result = "";
    while(i >= 0 || j >= 0) {
        var m = i < 0 ? 0 : a[i] | 0;
        var n = j < 0 ? 0 : b[j] | 0;
        carry += m + n; // sum of two digits
        result = carry % 2 + result; // string concat
        carry = carry / 2 | 0; // remove decimals,  1 / 2 = 0.5, only get 0
        i--;
        j--;
    }
    if(carry !== 0) {
        result = carry + result;
    }
    return result;
};

File

Answer 5

general solution that supports binary strings of different lengths

I've added a padZeroes() function to Cassandra Wilcox's nice answer to create a general solution that supports binary strings of different lengths 🎉

I've tested this solution against the add binary problem on leetcode, so it should be pretty robust.

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */

// logic gates
function xor(a, b) {
  return a === b ? 0 : 1;
}

function and(a, b) {
  return a == 1 && b == 1 ? 1 : 0;
}

function or(a, b) {
  return a || b;
}

function halfAdder(a, b) {
  const sum = xor(a, b);
  const carry = and(a, b);
  return [sum, carry];
}

function fullAdder(a, b, carry) {
  halfAdd = halfAdder(a, b);
  const sum = xor(carry, halfAdd[0]);
  carry = and(carry, halfAdd[0]);
  carry = or(carry, halfAdd[1]);
  return [sum, carry];
}

function padZeroes(a, b) {
  const lengthDifference = a.length - b.length;
  switch (lengthDifference) {
    case 0:
      break;
    default:
      const zeroes = Array.from(Array(Math.abs(lengthDifference)), () =>
        String(0)
      );
      if (lengthDifference > 0) {
        // if a is longer than b
        // then we pad b with zeroes
        b = `${zeroes.join('')}${b}`;
      } else {
        // if b is longer than a
        // then we pad a with zeroes
        a = `${zeroes.join('')}${a}`;
      }
  }
  return [a, b];
}

function addBinary(a, b) {
  let sum = '';
  let carry = '';

  const paddedInput = padZeroes(a, b);
  a = paddedInput[0];
  b = paddedInput[1];

  for (let i = a.length - 1; i >= 0; i--) {
    if (i == a.length - 1) {
      // half add the first pair
      const halfAdd1 = halfAdder(a[i], b[i]);
      sum = halfAdd1[0] + sum;
      carry = halfAdd1[1];
    } else {
      // full add the rest
      const fullAdd = fullAdder(a[i], b[i], carry);
      sum = fullAdd[0] + sum;
      carry = fullAdd[1];
    }
  }
  return carry ? carry + sum : sum;
}

Corduroys

Answer 6

instead of dealing with binary, we can convert them to decimal numbers and perform any arithmetic operation then convert back to binary again.

function calculateBinary(expr){
    let [pre,post]=expr.split(/[+|\-|\*|\/]/).map(binary=>parseInt(parseInt(binary, 2).toString(10).trim()));
    let sign=expr.match(/[+|\-|\*|\/]/)[0];
    let res=eval(pre+sign+post);
    return res.toString(2);
}
console.log(calculateBinary('11011+1000'))//=>100011
console.log(calculateBinary('1000-0100'))//=>100
console.log(calculateBinary('1000/0100'))//=>10
console.log(calculateBinary('10*10'))//=>100

Ningpo

Answer 7

Just in my opinion，it is because those nums are too large to lose precision.

var addBinary = function(a, b) {
    var dec = Number(parseInt(a, 2)) + Number(parseInt(b, 2));
    console.log("the number a is " + parseInt(a, 2));
    console.log("the number b is " + parseInt(b, 2));
    console.log("the dec is  " + dec);
    return dec.toString(2);
};
var a = "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
var b = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"
console.log(addBinary(a, b));

the result is

the number a is 2.484789315402498e+28
the number b is 5.2670055459872975e+29
the dec is  5.515484477527547e+29
110111101100010011000101110110100000011101000101011000000000000000000000000000000000000000000000000

You can see the numa and numb both loss precision.If converting the last result to binary:

 parseInt("110111101100010011000101110110100000011101000101011000000000000000000000000000000000000000000000000", 2)

then you get :

 5.515484477527547e+29. 

so the process of "toString(2)" is right.

we manually simulate the process of the binary to solve this problem(suppose the input string is right, so I don't catch any exception in my code. The runtime environment is nodejs v4.6.0):

"use strict"
let addBinarybyChainhelen = function(a, b) {
    let alen = a.length;
    let blen = b.length;

    let i = alen - 1;
    let j = blen - 1;

    let result  = "";
    let carry   = 0;

    while(i >= 0 && j >= 0) {
        let acur = parseInt(a[i], 10);
        let bcur = parseInt(b[j], 10);

        let rcur = (acur + bcur + carry) % 2;
        carry = parseInt((acur + bcur + carry) / 2); 

        result += rcur;

        i--;
        j--;
    }

    while(i >= 0) {
        let acur = parseInt(a[i], 10);
        let rcur = (acur + carry) % 2;
        carry = parseInt((acur + carry) / 2); 

        result += rcur;
        i--;
    }

    while(j >= 0) {
        let bcur = parseInt(b[j], 10);
        let rcur = (bcur + carry) % 2;
        carry = parseInt((bcur + carry) / 2); 

        result += rcur;
        j--;
    }

    if(carry) {
        result += carry;
    }

    return result.split("").reverse().join("");
}


// use the function
let a = "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101" 
let b = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"
console.log(addBinarybyChainhelen(a, b))

and get supposed correct output

110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000

Newsstand

this answer must be accepted, simple and working well. – Undersecretary

Answer 8

parseInt is possible to cause a problem that bigger than a max integer.

The solution is BigInt.

(BigInt('0b' + a) + BigInt('0b' + b)).toString(2);

almost similar to

(parseInt(a, 2) + parseInt(b, 2)).toString(2)

but it can handle more.

Lucarne

great point on the BigInt vs parseInt! I found that I needed BigInt to avoid errors. – Belsky

Answer 9

This is my solution, using a couple of conditional statements.

function addBinary(a, b) {
  let result = "";
  let i = a.length - 1;
  let j = b.length - 1;
  let carry = 0;

  while (i >= 0 || j >= 0 || carry > 0) {
    const x = parseInt(a[i], 10) || 0;
    const y = parseInt(b[j], 10) || 0;
    const z = x + y + carry;
    i--, j--;

    // error handling: non-binary number
    if (z > 3 || z < 0) return console.error("non-binary number");

    result = z === 3 || z === 1 ? 1 + result : 0 + result;
    carry = z < 2 ? 0 : 1;
  }

  return result;
}

The logic of the conditional statements is the same as using the following switch/case:

switch (z) {
   case 3:
      result = 1 + result;
      carry = 1;
      continue;
   case 2:
      result = 0 + result;
      carry = 1;
      continue;
   case 1:
      result = 1 + result;
      carry = 0;
      continue;
   case 0:
      result = 0 + result;
      carry = 0;
      continue;
   default:
      return console.error("non-binary number");
}

Upwind

absolutely brilliant this solution is. – Predella

Answer 10

This is my try ... Nothing fancy simple logic.

var addBinary = function(a, b) {
  let aLast = a.length - 1;
  let bLast = b.length - 1;

  let carry = 0;
  let aStr = [];

  while(aLast>=0 || bLast>=0){
    let sum = carry;
    if(aLast >= 0) {
      sum+= Number(a[aLast]);
      aLast--;
    }

    if(bLast >= 0) {
      sum+= Number(b[bLast]);
      bLast--
    }
    aStr.push(sum%2);
    carry = Math.floor(sum/2);
  }

  if(carry)     aStr.push(carry);

  return aStr.reverse().join("");
};

Fraley

Answer 11

I would like to add my solution as well

let a = '1111';
let b = '1111';
let addBinary = (a, b) => {

  let highestNumber;
  let lowestNumber;
  let answer = '';
  let carry = 0;

	let aArr = a.split('');
  let bArr = b.split('');
  
  if(aArr.length > bArr.length) {
  
  	highestNumber = aArr;
    lowestNumber = bArr;
  } else {
  
  	highestNumber = bArr;
    lowestNumber = aArr;
  }
  
  let diff = highestNumber.length - lowestNumber.length;
  let startingInd = highestNumber.length - diff;
  
  
  for(let i= startingInd; i < highestNumber.length; i++) {
  
  	lowestNumber = ['0'].concat(lowestNumber);
    
  }
  
  
  for(let i=highestNumber.length-1; i >= 0; i--) {
    
    let num1 = parseInt(highestNumber[i]);
    let num2 = parseInt(lowestNumber[i]);
    let sum = num1 + num2 + carry;
    
    let currValue = sum === 1 || sum === 3 ? '1' : '0';
    
    answer = currValue.concat(answer);
    
    
    if(sum === 3 || sum === 2) carry = 1;
    
  }
  
  if(carry == 1) answer = '1'.concat(answer);
  if(carry == 2) answer = '10'.concat(answer);
  
  return answer;
  
};


console.log(addBinary(a, b));

Viccora

Answer 12

I would like to propose the top most shortness variant in ES6 (the main requirements was to "avoid using built-in big integers to solve this challenge"):

// It's my challenge solution with 104 chars only:
addBinaryStrings = ([...a], [...b]) => {
    c = 0
    r = ''
    while (a[0] | b[0] | c) {
        c += ~~a.pop() + ~~b.pop()
        r = c%2 + r
        c = c > 1
    }
    return r
}

// Test:
binaryString1 = "1010110000000001101011001000010110101111110010100011011100101010000101011010001110011001011110111"
binaryString2 = "10100110100001100010010001111100001110100110111001100001011010011000101111001110100011101110000100100010001100110000001010011000100110"

string1.innerText = binaryString1;
string2.innerText = binaryString2;
expected.innerText = "10100110100001100010010001111100001111111100111001101110110011011011100101001100111000001001101001110010111000000001111101100100011101"
result.innerText = addBinaryStrings(binaryString1, binaryString2)

* {
  font-family: monospace;
}

div b {
  color: red;
}
div span {
  color: dodgerblue;
}

<div>BINARY&nbsp;1:&nbsp;<b id="string1"></b></div>
<div>SUMM&nbsp;&nbsp;&nbsp;&nbsp;:&nbsp;<span>+</span></div>
<div>BINARY&nbsp;2:&nbsp;<b id="string2"></b></div>
<div>FINALLY&nbsp;:&nbsp;<span>=</span></div>
<div>EXPECTED:&nbsp;<span id="expected"></span></div>
<div>RESULT&nbsp;&nbsp;:&nbsp;<span id="result"></span></div>

Santasantacruz

Answer 13

just convert to int and convert again to bin

var addBinary = (a, b) => {
    var dec = Number(parseInt(a, 2)) + Number(parseInt(b, 2));
    return (dec >>> 0).toString(2);
};

console.log(addBinary(1000,11));

Boaz

This answer would would be improved by the addition of an explanation – Cuthbert

Answer 14

var addBinary = function(a, b) {
    let res = ""
    let carry = 0

    while(a || b || carry){
        let temp = +a.slice(-1) + +b.slice(-1) + carry
        res = temp%2 + res
        carry = temp>1 ? 1 : 0
    
        a = a.slice(0,-1)
        b = b.slice(0,-1)
    }
    return res
}

Try this code

Dung

Answer 15

var addBinary = function(a, b) {
      return (BigInt("0b" + a) + BigInt("0b" + b)).toString(2);
};

Here, BigInt("0b" + a) and BigInt("0b" + b) directly convert the binary strings a and b to BigInt, using the "0b" notation to indicate that they are binary numbers.

This will print the right answer in all cases.

Countrybred

Answer 16

Here is a simple solution, given a and b are two binary strings, return their sum also in binary string.

let addBinary = (a, b) => {
  // handle corner cases when either input is empty
  if (a === null || a.length === 0) return b;
  if (b === null || b.length === 0) return a;

  let i = a.length - 1;
  let j = b.length - 1;
  let carry = 0;
  let sum = '';

  while (i >=0 || j >= 0) {
    let x = i < 0 ? 0 : +a[i];
    let y = j < 0 ? 0 : +b[i];
    let val = x + y + carry;

    carry = val > 1 ? 1 : 0;
    sum = val % 2 + sum;

    i--;
    j--;
  }

  return carry > 0 ? carry + sum : sum;
};

Some basic rules in regards to binary addition:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 0, carry = 1

Hopefully this can be helpful!

Leicester

as written, this function returns "0" when we would expect "1": addBinary("0", "1"); // "1" – Corduroys

Answer 17

Simple and Naive solution for adding 2 n-length binary integers:

function binaryAddition(num1, num2) {
  let result = [];
  let carry = 0;
  for(let i = num1.length-1; i >= 0; i--) {
    if((num1[i] === 1 && num2[i] === 1)) {
      if(carry) {
       result.unshift(1) 
      } else {
       result.unshift(0);  
      }
      carry = 1;
    } else if((num1[i] === 0 && num2[i] === 0)) {
      if(carry) {
       result.unshift(1) 
      } else {
       result.unshift(0);  
      } 
      carry = 0;
    } else if((num1[i] === 1 && num2[i] === 0) || (num1[i] === 0 && num2[i] === 1)) {
      if(carry) {
       result.unshift(0)
       carry = 1;
      } else {
       result.unshift(1);  
      }
    }  
  }
  if(carry) result.unshift(1);
  return result;
}

Blastopore

fails for case addBinary(11, 1); // 100 and case addBinary(0, 1); // 1 – Corduroys

Answer 18

You can Solve it like Below:

let addBinary = (a,b)=> parseInt(a,2)*parseInt(b,2).toString(2);

That's it

Dotard