二进制求和

Tips

相关题目:

• 43. 字符串相乘(大数相乘)
• 415. 字符串相加(大数相加)
• 445. 两数相加 II(大数相加链表版)

题目

给你两个二进制字符串 a 和 b, 以二进制字符串的形式返回它们的和. 即二进制版的大数相加.

提示:

• 1 <= a.length, b.length <= 10⁴
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0", 就不含前导零

题解

JavaScript

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
  const n = Math.max(a.length, b.length)

  a = a.padStart(n, 0)
  b = b.padStart(n, 0)

  let carry = 0
  let res = ''

  for (let i = n - 1; i >= 0; i--) {
    const sum = +a[i] + +b[i] + carry
    carry = (sum / 2) | 0
    res = (sum % 2) + res
  }

  return carry === 0 ? res : `1${res}`
}

tip

ES10 出了一个新的基础类型 BigInt.

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

Rust

use std::cmp;

pub fn add_binary(a: String, b: String) -> String {
    let n = cmp::max(a.len(), b.len());
    let mut a = a;
    let mut b = b;

    for i in 0..(n - a.len()) {
        a.insert(0, '0');
    }

    for i in 0..(n - b.len()) {
        b.insert(0, '0');
    }

    let a = a.as_bytes();
    let b = b.as_bytes();

    let mut carry = 0;
    let mut res = String::new();

    for i in (0..n).rev() {
        let sum = (a[i] - b'0') as i32 + (b[i] - b'0') as i32 + carry;
        carry = sum / 2;
        res.insert_str(0, &(sum % 2).to_string());
    }

    if carry == 0 {
        res
    } else {
        res.insert_str(0, "1");
        res
    }
}