19 - 二进制求和

题目

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1" 输出: "100"

示例 2:

输入: a = "1010", b = "1011" 输出: "10101"

解答

作者：guanpengchn

链接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-67-er-jin-zhi-qiu-he-by-guanpengch/

var addBinary = function(a, b) {
    let ans = "";
    let ca = 0;  // 进位
    for(let i = a.length - 1, j = b.length - 1;i >= 0 || j >= 0; i--, j--) {
          // 直到长的那个字符串遍历完
        let sum = ca;  // 保留进位
        sum += i >= 0 ? parseInt(a[i]) : 0;  // 如果字符串跑完了，就补0
        sum += j >= 0 ? parseInt(b[j]) : 0;
        ans += sum % 2;   // 算出当前位
        ca = Math.floor(sum / 2);
    }
    ans += ca == 1 ? ca : "";   // 如果跑完了所有进位，还有进位，就补上
    return ans.split('').reverse().join('');  // 反转字符串
};

Runtime: 64 ms, faster than 78.60% of JavaScript online submissions for Add Binary.

Memory Usage: 35.8 MB, less than 45.62% of JavaScript online submissions for Add Binary.

之前研究了无符号进位，感觉10行还能再装逼一点：

...
    ca = sum >>> 1
...

意思就是，sum是正数，那么>>>1就能让他除二，并取floor，结果是一样的。

失败的直接法

拿到题目，首先想到的，就是二进制转成十进制，加完后在转成二进制。

2转10就用parseInt，在第二个参数写2。10转2，就在后面接.toString(2)就可以了。如(12).toString(2)

为什么数字要加括号才能用这个方法？不加就会报错？

image-20190716110639706

一开始的理解是，这个数字是值类型，因此.__proto__指不到任何地方，也没有方法可以继承。

但是难以解释这个情况：

image-20190716124943536

这说明，这个2是一个数字对象，并且有toString这个继承了的方法。

image-20190716125048945

因此，这里的报错，是因为对于.的解释有歧义。参考这篇文章

这个.，可以理解为小数点，也可以理解为对象的属性访问器。在这里，解析器是把小数点后面的toString(2)，理解为了小数点。而这并非数字，因此出错。

官网上也找到了类似的说法：

image-20190716125317932

那么值类型为什么是个对象呢？对象不是引用类型吗？参考

官网是这么说的：

2和Number(2)都是基本数字(primitives)。但你要用方法的时候，js会自动将其转成数字对象(objects)，就能用自带的方法了。

利用 valueOf 方法，我们能将象转换成其对应的基本类型。

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
  var a_10 = parseInt(a, 2);
  var b_10 = parseInt(b, 2);
  return parseInt(a_10 + b_10).toString(2);
};

但是如果转成十进制的时候，超过了最大安全数（$2^{53}-1$，即9007199254740991），就会出现结果错误的问题。

反例：

// 输入：
[      "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101",  （2.484789315402498e+28）
 "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"（5.2670055459872975e+29）
]
// 答案：
"110111101100010011000101110110100000011101000101011001000011011000001100011110011010010011000000000"（1.1011110110001001e+98）
// 结果是
"101"（5）

十进制转二进制的精度问题

js浮点数运算精度问题

js浮点数陷阱

能被转化为有限二进制小数的十进制小数的最后一位必然以 5 结尾(因为只有 0.5 * 2 才能变为整数)。所以十进制中一位小数 0.1 ~ 0.9 当中除了 0.5 之外的值在转化成二进制的过程中都丢失了精度。（因为陷入了循环）

在 JavaScript 中所有数值都以 IEEE-754 标准的 64 bit 双精度浮点数进行存储的

image-20190714220841347

符号位决定了一个数的正负，指数部分决定了数值的大小，小数部分决定了数值的精度。

用BigInt也解决不了。。精度不够，结果的末尾是一堆0……

var addBinary = function(a, b) {
  var a_10 = BigInt(parseInt(a, 2));
  var b_10 = BigInt(parseInt(b, 2));
  return BigInt(parseInt(a_10 + b_10)).toString(2);
};
image-20190716102140406
Previous16 - 最大子序和Next12 - 移除元素

Last updated

Was this helpful?