手记

前端面试总结(算法篇)- 1

问题:实现超出整数范围的相加计算。

剖析

为了深入理解这个问题,我们要解决一下三点:

  1. 为什么会有最大范围,最大范围是多少?
  2. 如何实现超整数相加?
  3. 【延伸】浮点数精度问题?

一、为什么会超出?

众所周知现在我们的计算机基本都进入了64位的处理器时代,这里的64位表示着每个时钟周期能处理64个电信号。而对于存储数字来说(内存地址),我们一般都是用64位二进制记录,因为精度已经足够了。而规定这个范围的就是 - 电气和电子工程师协会(IEEE,全称是Institute of Electrical and Electronics Engineers)。

IEEE 一个国际性的电子技术与信息科学工程师的协会,是目前全球最大的非营利性专业技术学会,其会员人数超过40万人,遍布160多个国家。IEEE致力于电气、电子、计算机工程和与科学有关的领域的开发和研究,在太空、计算机、电信、生物医学、电力及消费性电子产品等领域已制定了900多个行业标准,现已发展成为具有较大影响力的国际学术组织。

也就是最近将华为赶出委员会的 IEEE ,其中 IEEE 754 就是服务于存储数字的 二进制浮点数算术标准 。这个标准定义了表示浮点数的格式(包括负零-0)与反常值(denormal number)),一些特殊数值(无穷(Inf)与非数值(NaN)),以及这些数值的“浮点数运算符”;它也指明了四种数值舍入规则和五种例外状况(包括例外发生的时机与处理方式)。

IEEE 754 规定了四种表示浮点数值的方式:单精确度(32位)、双精确度(64位)、延伸单精确度(43比特以上,很少使用)与延伸双精确度(79比特以上,通常以80位实现)。而JavaScript中只有一种类型数,即64位(1bit 的符号位,11bits 的指数部分 ,以及52bits 的小数部分)双精度浮点数,当数值超过这个范围时,就会发生精度丢失。

符号位决定正负,指数部分决定数值的大小,小数部分决定数值的精度。 IEEE 754规定,有效数字第一位默认总是1,不保存在64位浮点数之中。也就是说,我们的能表示的唯一整数范围在 -2^53-1 ~ +2^53-1(不包括边界)。

这样就引发我们最开始的问题,如何实现超出整数范围的相加计算?

二、解题思路

既然没办法直接用 Number 表示这个数,很显然我们使用字符串来记录这个超整数的,回忆一下我们小学时学的加法进位,满十进一。

function oversizeAdd(str1, str2) {
    var arr1 = str1.split(''), //将字符串转成数组存储
        arr2 = str2.split(''),
        extra = false, //是否有进位
        sum, //各位相加和
        res = ''; //最后字符串记录答案

    while(arr1.length || arr2.length || extra) {
        sum = ~~arr1.pop() + ~~arr2.pop() + extra //~位运算符(按位取反),~~将字符串转换成数字
        res = sum % 10 + res
        extra = sum > 10
    };

    return res
};

代码的其他部分都是很好懂的,有趣的是这个位运算 ~~,要转成整数不能用 parseInt() 或者 Number() 吗?两个位数相同的超整数还好说,要是位数不用,其中一个减到最后为空数组了,pop() 就会返回 undefined 那就会被转成 NaN,这明显是不对的,这时我们利用 ~~ 做到了将 undefined 转成 数字零的效果。

其他位运算的妙用:

//两个整数交换
var  a = 10,b=20;  //^=是异或运算,相同取0,不同取1.
a ^= b; b^=a;a^=b;

//等同于
var a = 1,b = 2;
a = a + b;
b = a - b;
a = a - b;
a // 2
b //1 

三、浮点数精度问题

无论什么语言只要是遵循 IEEE 754 标准就会有浮点数精度问题,最经典的例子就是:

    0.1 +0.2 != 0.3
    0.3 + 0.6 = 0.8999999999999999
    0.3 - 0.2 = 0.09999999999999998
    0.3 * 1.5 = 0.44999999999999996
    0.3 / 0.1 = 2.9999999999999996

像0.3这种小数转换为二进制位数是无穷的(有循环),因最多只有52位所以超出的部分被截除,导致了精度的问题。

一般我们用 toFixed 或者先成10再除10这种升级小数的方法

  1. (0.1+0.2).toFixed(2) == 0.3 //true
  2. (0.1*10+0.2*10)/10 == 0.3

当然两个都是有bug的

  1. 1.335.toFixed(2) // 1.33 错误
  2. 35.41 * 100 = 3540.9999999999995

思路

toFixed是不行的了,那只剩优化小数升级这招,上面做超整数时我们就知道用字符串就不会有Number计算不准确这个问题啦。

【核心】将浮点数转成字符串并记录小数位数

var floatAdd = (num1, num2) => {
      let arr1 = num1.toString(),
        arr2 = num2.toString(),
        res = "";

      //补位
      if (arr1.length > arr2.length) {
        arr2 = arr2 + "0".replace(arr1.length - arr2.length);
      } else if (arr1.length < arr2.length) {
        arr1 = arr1 + "0".replace(arr2.length - arr1.length);
      }

      //记录小数长度
      let len = arr1.length - arr1.indexOf(".") - 1;

      arr1 = parseInt(arr1.replace(".", ""));
      arr2 = parseInt(arr2.replace(".", ""));

      res = (arr1 + arr2) / Math.pow(10, len);

      return res;
    };

floatAdd(0.1,0.2) //0.3
1人推荐
随时随地看视频
慕课网APP