JavaScript：添加两个二进制数（返回二进制）

Question

我有两个二进制输入，将返回二进制的加法结果。

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

对于一些非常大的二进制数，例如

a = 10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101

b = 110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011

我输出的结果是

110111101100010011000101110110100000011101000101011000000000000000000000000000000000000000000000000

而正确的输出应该是

110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000

这是因为溢出了吗？如果是，JavaScript中二进制加法溢出的限制是什么？很抱歉有这么多的1和0。

- patrickhuang94

---

JavaScript 由于只有 53 位的限制，因此会出现溢出操作。这个问题可能会为您提供答案：https://dev59.com/a10a5IYBdhLWcg3wH1py - user2417483

你不需要那些 Number 调用。parseInt 已经返回数字了。 - Bergi

Answer 1

我已经使用JavaScript开发了一个二进制加法的解决方案。

我的初始目标是通过在JavaScript中复制数字二进制加法器电路中使用的机制来巩固对二进制逻辑的理解（不使用基数转换或位运算符）。

您可以在CodePen上找到我原始项目的可工作版本。

它处理DOM比您可能需要的要多，但当我插入您的数字（使用下面提到的调整），我很高兴看到它起作用了！

可行的解决方案代码 << 这个项目由我的原始项目修改而来，仅包含输出正确答案所需的代码。

此解决方案假定a和b是相同长度的字符串。要使用此解决方案，您的输入变量应进行修改：

var a = "000010100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"

var b = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"

我刚刚在var a前面用0填充了缺失的数字。

正如你所看到的，我重新创建了二进制加法电路实现中使用的所有组件：

半加器：

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 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 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;
}

那么，addBinary(a,b)会产生正确的答案！

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

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

我希望我在这里所做的一些事情也能对你有所帮助！

- Cassandra Wilcox

---

不错！我对此进行了迭代，并添加了支持不同长度的二进制字符串 :-) https://dev59.com/olkS5IYBdhLWcg3wHTJy#46477181 - Micah Stubbs

Answer 2

我的看法：

这个逻辑很简单，就像在小学里学的一样，从最右边的数字开始：我加上第一个数字的最后一位和第二个数字的最后一位，并保留进位到下一轮。

在每一轮（while 内部）中，我都会右侧修剪两个数字，例如：

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

输入和输出均为字符串，以克服JS的最大整数限制，其中字符串的长度可以更大。

完整代码：

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";

- vsync

---

请问您能解释一下这里 a.slice(-1) 前面的加号有什么作用吗？ - Daniel Williams

@DanielWilliams - 这是一种将String转换为整数Number的“技巧”。如果在一个字符串前进行数学运算，Javascript会将该表达式作为数字进行计算。 - vsync

Answer 3

受@thepatriot的启发，我使用BigInt对象创建了一个单行版本。

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

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

- Penny Liu

Answer 4

忘掉Javascript的操作精度，思考如何在数学上加一二进制。

例如：11 + 10。

首先，我们应该从右向左开始。 现在我们得到 1 + 0 = 1 之后，我们继续下一个。 1 + 1 = 10 如果我们使用Javascript，如何得到结果。

我们知道，Mod可以得到余数，Division可以得到进位。 在十进制系统中，我们得到1 + 1 = 2，如何将2转换为10。 我们可以使用

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

现在我们只需要将这两个字符串拼接在一起即可。

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

所以我们的最终代码可以是这样的：

/**
 * @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;
};

- HectorGuo

Answer 5

我们可以将二进制数转换成十进制数来进行任何算术运算，然后再将其转换回二进制数，而无需直接处理二进制数。

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

- Sheikh Salman

Answer 6

支持不同长度二进制字符串的通用解决方案

我已经在Cassandra Wilcox的好答案中添加了一个padZeroes()函数，以创建一个支持不同长度二进制字符串的通用解决方案。

我已经在leetcode上对这个解决方案进行了添加二进制问题的测试，所以它应该非常健壮。

/**
 * @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;
}

- Micah Stubbs

Answer 7

我认为，这是因为这些数字太大，会失去精度。

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 number a is 2.484789315402498e+28
the number b is 5.2670055459872975e+29
the dec is  5.515484477527547e+29
110111101100010011000101110110100000011101000101011000000000000000000000000000000000000000000000000

您可以看到numa和numb都失去了精度。如果将最后的结果转换为二进制：

 parseInt("110111101100010011000101110110100000011101000101011000000000000000000000000000000000000000000000000", 2)

那么您将得到：

 5.515484477527547e+29. 

因此，“toString(2)”的过程是正确的。

我们手动模拟二进制转换的过程来解决这个问题（假设输入字符串是正确的，所以我在代码中没有捕获任何异常。运行环境是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))

并获得预期的正确输出

110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000

- chainhelen

---

此回答必须被接受，简单有效。 - Murali Krishna

Answer 8

parseInt 可能会导致超出最大整数的问题。

解决方案是使用 BigInt。

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

几乎类似于

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

但它可以处理更多。

- xyh

---

关于 BigInt vs parseInt 的观点很好！我发现需要使用 BigInt 来避免错误。 - thetipsyhacker

Answer 9

我想提出ES6中最短的变体（主要要求是“避免使用内置的大整数来解决这个挑战”）：

// 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>

- Vladimir Fedorov

Answer 10

我也想添加我的解决方案

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

- Senal