亿题

基准测试

var Benchmark = require("benchmark");
var suite = new Benchmark.Suite();
var arr = [];

suite
    .add("fn1", function () {
        fn1(arr);
    })
    .add("fn2", function () {
        fn2(arr);
    })
    .on("cycle", function (event) {
        console.log(String(event.target));
    })
    .on("complete", function () {
        console.log("本次测试数组长度:" + arr.length + ", 最快的算法是:" + this.filter("fastest").map("name"));
    })
    // run async
    .run({ async: true });

// name 每秒执行次数 统计误差以及相对最好的慢了多少(%)抽样数量

// fn1 x 13,582,301 ops/sec ±0.61% (85 runs sampled)
// fn2 x 10,924,324 ops/sec ±1.23% (87 runs sampled)
// 本次测试数组长度:49, 最快的算法是:pch.reverse
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

下面哪一种是闭包?

// 1
function fn() {
    var value = 1;
    return {
        fn: () => {
            return value;
        }
    };
}
// 2
function fn() {
    var value = 1;
    return {
        fn: value
    };
}

// 3
function fn() {
    var fn2 = (_) => 1;
    return {
        fn2: fn2
    };
}

// 4
function fn() {
    return (_) => 1;
}

// 5
function fn() {
    fn = function () {};
}

// 6
function fn() {}
setTimeout(fn);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

对象属性查找

// 实现一个函数 find(obj, str),满足:
var obj = { a: { b: { c: 1 } } };
find(obj, "a.b.c"); // 1
find(obj, "a.d.c"); // undefined

function find(obj = {}, attrs = "") {
    var arr = attrs.split("."); // ['a','b','c']
    var i = 0;
    var val = obj[arr[i]];
    while (typeof val === "object") {
        val = val[arr[++i]];
    }
    return val;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

this&call?

function fn() {
    console.log(this);
}
fn.call(undefined); // global
fn.call(null); // global
fn.call({}); // {}
fn.apply(undefined); // global
fn.apply(null); // global
fn.apply({}); // {}

/**
 * 结论:this 只能是 global 或者 某个对象
 */
1
2
3
4
5
6
7
8
9
10
11
12
13

闭包&运算符?

var a = 0,
    b = 0;
function A(a) {
    // 此处产生闭包,形参 a 是私有属性
    A = function (b) {
        console.log(a + b++);
    };
    console.log(a++);
}
// 1 4

/**
 * 结论:闭包就是在嵌套函数外部可以访问内部函数的一种形式。
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14

this&global?

this.a = { b: 2 };
console.log(a); // { b: 2 }

var a = 1;
(function fn() {
    var a = 2;
    console.log(a); // 2
})();
(function fn() {
    this.a = 3;
    console.log(a); // 3
})();
(function fn() {
    var a = 2;
    this.a = 3;
    console.log(a); // 2
})();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

数组快速排序

function fastSort(arr, left, right) {
    let exchange = (arr, i, j, tmp) => {
        // 数组项位置互换
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    };
    let baseIndex = left; // 基准索引位置
    let nextIndex = left + 1; // 操作索引位置
    if (left < right) {
        // 符合条件检测
        for (let i = nextIndex; i <= right; i++) {
            // 从操作索引位置开始遍历
            if (arr[i] < arr[baseIndex]) {
                // 符合条件检测
                exchange(arr, i, nextIndex); // 数组项位置互换
                nextIndex++; // 操作索引位置,指向下一个
            }
        }
        nextIndex--; // 操作索引位置,下一个不存在,指回上一个
        exchange(arr, baseIndex, nextIndex); // 数组项位置互换,得到左右两个大小片段
        fastSort(arr, left, nextIndex - 1); // 递归处理小片段
        fastSort(arr, nextIndex + 1, right); // 递归处理大片段
    }
    return arr; // 上述同步代码,完成后返回变更的原数组
}

// -------------------测试
const getNumber = (min = 0, max = 99) => {
    if (min === 0) return Math.round(Math.random() * max);
    return Math.round(Math.random() * (max - min)) + min;
};
const len = 50;
const arr = new Array(len).fill(1).map(() => getNumber(1, len));
fastSort(list, 0, list.length - 1);
console.log(arr);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

数组扁平

// 递归
function flatLoop(arr, newArr = []) {
    for (let index = 0; index < arr.length; index++) {
        if (Array.isArray(arr[index])) {
            flatLoop(arr[index], newArr);
        } else {
            newArr.push(arr[index]);
        }
    }
    return newArr;
}
// 内循环
function flatWhile(arr) {
    var newArr = [];
    while (1) {
        var loopArr = [];
        var hasInnerArr = false;
        arr.forEach((element) => {
            if (Array.isArray(element)) {
                hasInnerArr = true;
                loopArr = loopArr.concat(element);
            } else {
                newArr.push(element);
            }
        });
        arr = loopArr;
        if (!hasInnerArr) break;
    }
    return newArr;
}

// 使用 reduce、concat 和递归展开无限多层嵌套的数组
function flatDeep(arr, d = 1) {
    return d > 0
        ? arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatDeep(val, d - 1) : val), [])
        : arr.slice();
}
const flatten = function (arr) {
    while (arr.some((item) => Array.isArray(item))) {
        arr = [].concat(...arr);
    }
    return arr;
};

const flatStr = function (arr) {
    return arr
        .join(",")
        .split(",")
        .map((item) => Number(item));
};

// flatWhile x 4,066 ops/sec ±1.39% (80 runs sampled)
// flatLoop x 71,494 ops/sec ±0.46% (89 runs sampled)
// flatArray x 5,459 ops/sec ±0.80% (85 runs sampled)
// flatDeep x 70,783 ops/sec ±0.43% (91 runs sampled)
// flatten x 11,442 ops/sec ±0.48% (89 runs sampled)
// flatStr x 5,107 ops/sec ±0.59% (87 runs sampled)
// 最快的算法是:flatLoop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

数组排序

[].sort((pre, next) => pre - next);
1

更多排序算法请移步本站的算法研究/排序

数组去重

const fn1 = (arr) => [...new Set(arr)];
const fn2 = (arr) => Array.from(new Set(arr));
const fn3 = (arr) => {
    let obj = {};
    for (let i = 0; i < arr.length; i++) {
        if (obj[arr[i]]) {
            arr[i] = arr[arr.length - 1];
            arr.length--;
            i--;
            continue;
        }
        obj[arr[i]] = arr[i];
    }
    return arr;
};
const fn4 = (arr) => {
    let newArr = [];
    for (let i = 0; i < arr.length; i++) {
        let cur = arr[i];
        // if (!newArr.includes(cur)) {
        if (newArr.indexOf(cur) === -1) {
            newArr.push(cur);
        }
    }
    return newArr;
};
const fn5 = (arr) => {
    let newArr = [];
    arr.sort();
    arr.forEach((value, key) => {
        if (value !== arr[key + 1] || key === arr.length) {
            newArr.push(value);
        }
    });
    return newArr;
};
const fn6 = (arr) => {
    return arr.filter((value, key) => {
        return arr.indexOf(value) === key;
    });
};
const fn7 = (arr) => {
    return arr.reduce((valueList, value) => {
        return valueList.includes(value) ? valueList : [...valueList, value];
    }, []);
};

// 本次测试方案数量:7
// 本次测试数组长度:249
// fn2 x 422,390 ops/sec ±0.66% (90 runs sampled)
// fn1 x 428,055 ops/sec ±0.52% (91 runs sampled)
// fn3 x 1,844,590 ops/sec ±0.53% (90 runs sampled)
// fn7 x 2,858,151 ops/sec ±0.46% (81 runs sampled)
// fn5 x 3,104,046 ops/sec ±0.39% (89 runs sampled)
// fn6 x 11,623,413 ops/sec ±1.27% (86 runs sampled)
// fn4 x 12,381,346 ops/sec ±2.29% (84 runs sampled)
// 本次测试数组长度:6, 最快的算法是:fn4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

数组反转

function reverse(arr) {
    let halfLen = Math.floor(arr.length / 2);
    for (let i = 0; i < halfLen; i++) {
        var tmp = arr[i];
        arr[i] = arr[arr.length - 1 - i];
        arr[arr.length - 1 - i] = tmp;
    }
    return arr;
}
// pch.reverse x 3,343,691 ops/sec ±0.51% (89 runs sampled)
// Array.reverse x 1,473,960 ops/sec ±0.91% (88 runs sampled)
// 本次测试数组长度:677, 最快的算法是:pch_reverse
1
2
3
4
5
6
7
8
9
10
11
12

数组遍历

// 数组 [1,2,3,4,5,6,7,8,9]
var noop = (v) => console.log(v);
var noopFalse = (v) => noop(v) && false;
var arr = new Array(10).fill(1).map((value, index, arr) => index);
//
arr.map(noop);
arr.every(noop);
arr.forEach(noop);
arr.filter(noopFalse);
arr.some(noopFalse);
arr.reduce((sum, value) => noop(value));
arr.reduceRight((sum, value) => noop(value));
arr.find(noopFalse);
arr.findIndex(noopFalse);
for (var i = 0; i < arr.length; i++) noop(arr[i]);
for (var i in arr) noop(arr[i]);
for (var value of arr) noop(value);
while (arr.length) noop(arr.shift());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

数组生成双向二叉树

使用数组构建一颗二叉搜索树,然后使用递归中序方式遍历出来: 左节点 < 根节点 < 右节点

var arr = [5, 2, 6, 3, 7, 4, 9, 0, 1, 8];
console.log(createTree(arr));
/*
<ref *1> {
  left: null,
  right: <ref *2> {
    left: [Circular *1],
    right: { left: [Circular *2], right: [Object], value: 6 },
    value: 2
  },
  value: 5
}
*/

function createTree(arr) {
    // 根节点
    const root = {
        left: null,
        right: null,
        value: arr[0]
    };
    // 每一个节点都可能是根节点,所以存在循环引用关系,搞他
    const weak = new WeakMap();

    // 递归函数
    loop(root, 0);
    function loop(node, i) {
        // 缓存
        if (!weak.has(node)) weak.set(node, node);
        // 数组越界返回
        if (!arr[i]) return;
        // 数组遍历
        if (arr[i + 1]) {
            // 右节点初始化
            node.right = {
                // 左节点就是自己,循环引用关系
                left: weak.get(node),
                // 下一个右节点,占位
                right: null,
                // 右节点值
                value: arr[i + 1]
            };
            // 右节点为目标,递归
            loop(node.right, i + 1);
        }
    }
    // 返回二叉树
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

数组最大和的子串

实现 getMax([1, -2, 3, -4, -1, 2, 9]); // 11

同类的还有

  • 最小和的子串
  • 最长重复项子串
  • 最长不重复项子串
function getMax(arr) {
    // TODO
    var max = 0;
    for (var i = 0; i < arr.length; i++) {
        var tmpMax = arr[i];
        for (var j = i + 1; j < arr.length; j++) {
            tmpMax += arr[j];
            if (tmpMax > max) {
                max = tmpMax;
            }
        }
    }
    return max;
}
var obj = getMax([1, -2, 3, -4, -1, 2, 9]);
console.log(obj); // 11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

类数组转化为数组

类数组 拥有 length 属性,可枚举

[...arrayLike];
Array.from(arrayLike);
Array.prototype.slice.call(arrayLike);
Array.apply(null, arrayLike);
Array.prototype.concat.apply([], arrayLike);
1
2
3
4
5

对象数组(Object[])去重

/**
 * 数组去重
 * @param {array} arr 目标数组
 * @param {string} key 对象数组去重属性
 * @returns 新数组
 */
export function uniqueArray(arr = [], key = "") {
    if (!key) return [...new Set(arr)];
    const res = new Map();
    return arr.filter((obj) => !res.has(obj[key]) && res.set(obj[key], 1));
}
1
2
3
4
5
6
7
8
9
10
11

对象继承扩展

/**
 * 对象继承
 * 扩展对象原型方法
 */
export function objectExtend() {
    Object.prototype.extend = function (obj) {
        console.log("extend", this);
        Object.assign(this, obj);
    };
}
1
2
3
4
5
6
7
8
9
10

删除对象里的某些属性

/**
 * 删除对象里的某些属性
 * @param {object} obj 一个对象
 * @param {array} attrList 对象里可能存在的属性数组
 * @returns 变更后的对象
 */
export function delObjectAttr(obj, attrList = []) {
    for (const key in obj) {
        if (Object.hasOwnProperty.call(obj, key) && attrList.includes(key)) {
            delete obj[key];
        }
    }
    return obj;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

IIFE.name?

var b = 10;
(function b() {
    b = 20; // 失败,不报错
    console.log(b); // fn(){}
})();

// 1.IIFE中的函数是一个函数表达式,不是函数声明。
// 2.函数声明中的的函数名被绑定在它声明所在的作用域中。函数表达式中的函数名被绑定在函数自身的函数体中。
// 3.在函数表达式的内部只能通过函数名访问该函数,但是不能通过函数名对该函数重新赋值
1
2
3
4
5
6
7
8
9
var a = 10;
(function () {
    console.log(a);
    a = 5;
    console.log(window.a);
    var a = 20;
    console.log(a);
})();
// undefined
// 10
// 20
1
2
3
4
5
6
7
8
9
10
11

数组内两数字和

var arr = [4, 7, 11, 15, 4, 3, 15];

function findAll(arr, sum) {
    var map = {};
    var valueList = [];
    for (let i = 0; i < arr.length; i++) {
        var n = arr[i];
        if (map[sum - n] !== undefined) {
            map[sum - n].forEach((index) => {
                valueList.push(index + "-" + i);
            });
        }
        if (map[n]) {
            map[n].push(i);
        } else {
            map[n] = [i];
        }
    }
    return valueList;
}

function findOne(arr, sum) {
    var map = {};
    var valueList = [];
    for (let i = 0; i < arr.length; i++) {
        var n = arr[i];
        if (map[sum - n] !== undefined) {
            valueList = `${map[sum - n]}-${i}`;
            break;
        }
        map[n] = i;
    }
    return valueList;
}

console.log(findAll(arr, 8));
console.log(findOne(arr, 8));

console.log(findAll(arr, 26));
console.log(findOne(arr, 26));

console.log(findAll(arr, 11));
console.log(findOne(arr, 11));
// [ '0-4' ]
// 0-4
// [ '2-3', '2-6' ]
// 2-3
// [ '0-1', '1-4' ]
// 0-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

LRUcache?

设计一个(key:value)数据结构:

  • 先进先出,老人让给孩子座位
  • 最多存储(例如 20)
  • get(key:string):any
  • put(key:string, value:any):void

可以使用双向链表 + Object或者 Map 来存储插入顺序。

class LRUcache {
    constructor(max) {
        // 初始化最多存储(例如 20)
        this.max = max;
        // 初始化当前存储数量
        this.length = 0;
        // 初始化 key 的双向链表(包含属性: head、foot,方法:createNode、put、delete)
        this.keyLinkNode = new LinkNode(); // 双向链表
        // 初始化 map
        this.map = {
            // node
            // value
        };
    }
    get(key) {
        // 取值
        var value = this.map[key].value;
        // 取双向链表节点
        var node = this.map[key].node;
        // 删除数据
        delete this.map[key];
        // 处理链表
        this.keyLinkNode.delete(node);
        this.length--;
        // 返回结果
        return value;
    }
    put(key, value) {
        if (this.length === max) {
            // 链表必须拥有 foot 属性,达到 O(1) 复杂度操作
            this.get(this.keyLinkNode.foot.value);
        }
        // 处理链表
        var node = this.keyLinkNode.createNode(key);
        this.keyLinkNode.put(node);
        this.length++;
        // 处理 map
        this.map[key] = {
            value: value,
            node: node
        };
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

改造 Promise.all

  • 接收一个 Promise 数组,一个最大并行 Promise 等待数量
  • 从开始到结束,最大同试运行期约数不超过三个
  • 返回类似 Promise.all()的期约结果
// 一个 Promise 数组
var arr = [
    () =>
        new Promise((resolve, reject) => {
            setTimeout(() => {
                resolve(1);
            }, 1000);
        }),
    () =>
        new Promise((resolve, reject) => {
            setTimeout(() => {
                resolve(2);
            }, 1000);
        }),
    () =>
        new Promise((resolve, reject) => {
            setTimeout(() => {
                resolve(3);
            }, 1000);
        }),
    () =>
        new Promise((resolve, reject) => {
            setTimeout(() => {
                resolve(4);
            }, 1000);
        }),
    () =>
        new Promise((resolve, reject) => {
            setTimeout(() => {
                resolve(5);
            }, 1000);
        }),
    () =>
        new Promise((resolve, reject) => {
            setTimeout(() => {
                resolve(6);
            }, 1000);
        }),
    () =>
        new Promise((resolve, reject) => {
            setTimeout(() => {
                resolve(7);
            }, 1000);
        }),

    () => 8,
    () => () => {}
];
//
limitPromise(arr, 3).then(
    (valueList) => {
        // 完成,返回所有有序完成结果
        console.log("valueList", valueList);
    },
    (reason) => {
        // 拒绝,返回拒绝的原因
        console.log("reasonOne", reason);
    }
);
// 改造后
function limitPromise(arr, max) {
    var len = arr.length;
    return new Promise((resolve, reject) => {
        var i = 0;
        var valueList = [];
        var isRunLoop = false; // loop 只开启一次
        while (i < max) {
            console.log("while", i);
            ((j) => {
                var pm = arr[j]();
                // pm.then instanceof Function
                if (pm instanceof Promise) {
                    pm.then(
                        (value) => {
                            valueList[j] = value;
                            if (!isRunLoop) {
                                isRunLoop = true;
                                console.log("isRunLoop");
                                loop(j);
                            }
                        },
                        (reason) => {
                            reject(reason);
                        }
                    );
                } else {
                    valueList[j] = pm;
                    if (!isRunLoop) {
                        isRunLoop = true;
                        console.log("isRunLoop");
                        loop(j);
                    }
                }
            })(i);
            i++;
        }
        function loop(i) {
            console.log("loop", i, valueList);
            if (valueList.length === len) resolve(valueList);
            if (!arr[i]) return;
            // pm.then instanceof Function
            var pm = arr[i]();
            if (pm instanceof Promise) {
                pm.then(
                    (value) => {
                        valueList[i] = value;
                        loop(i + 1);
                    },
                    (reason) => {
                        reject(reason);
                    }
                );
            } else {
                valueList[i] = pm;
                loop(i + 1);
            }
        }
    });
}
/**
while 0
while 1
while 2
isRunLoop
loop 0 [ 1 ]
loop 1 [ 1, 2, 3 ]
loop 2 [ 1, 2, 3 ]
loop 3 [ 1, 2, 3 ]
loop 4 [ 1, 2, 3, 4 ]
loop 5 [ 1, 2, 3, 4, 5 ]
loop 6 [ 1, 2, 3, 4, 5, 6 ]
loop 7 [
  1, 2, 3, 4,
  5, 6, 7
]
loop 8 [
  1, 2, 3, 4,
  5, 6, 7, 8
]
loop 9 [ 1, 2, 3, 4, 5, 6, 7, 8, [Function (anonymous)] ]
valueList [ 1, 2, 3, 4, 5, 6, 7, 8, [Function (anonymous)] ]
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

版本号比较

var arr = ["0.1.1", "2.3.3", "0.302.1", "4.2", "2.3.3", "4.3.5", "4.3.4.5"];

function sortVersion(arr) {
    return arr.sort((a, b) => {
        var v1 = a.split(".");
        var v2 = b.split(".");
        var i = 0;
        while (1) {
            if (!v1[i] || !v2[i]) return !v1[i] ? -1 : 1;
            if (v1[i] === v2[i]) {
                i++;
                continue;
            }
            return v1[i] - v2[i];
        }
    });
}
console.log(sortVersion(arr));
// ['0.1.1', '0.302.1', '2.3.3', '2.3.3', '4.2',   '4.3.4.5', '4.3.5']
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Map 和 Object 区别

  • Map 默认不包含任何键
  • Map 键可以是任意值
  • Map 中的 key 是有序的。因此,当迭代的时候,一个 Map 对象以插入的顺序返回键值。
  • Map 是可迭代的

红绿灯

function light(i = 0) {
    var statusList = [
        { name: "红灯", delay: 1000 * 4 },
        { name: "绿灯", delay: 1000 * 3 },
        { name: "黄灯", delay: 1000 * 2 }
    ];
    var status = statusList[i];
    console.log("start ---", status.name);
    setTimeout(() => {
        console.log("end -----", status.name);
        light(i + 1 < 3 ? i + 1 : 0);
    }, status.delay);
}
light();
1
2
3
4
5
6
7
8
9
10
11
12
13
14

数组最长连续序列

输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

var arr = [100, 4, 200, 1, 3, 2];

function maxChain(arr) {
    let uniqueValues = {};
    let checkedValues = {};
    let max = 0;
    arr.forEach((i) => (uniqueValues[i] = 1));
    arr.forEach((i) => {
        // 过滤重复查找
        if (checkedValues[i]) return;
        checkedValues[i] = true;
        let left = i - 1;
        let right = i + 1;
        let _max = 1;
        // 向左查找
        while (uniqueValues[left]) {
            checkedValues[left] = true;
            left++;
            _max++;
        }
        // 向右查找
        while (uniqueValues[right]) {
            checkedValues[right] = true;
            right++;
            _max++;
        }
        // 最大值检出
        max = Math.max(max, _max);
    });
    return max;
}

console.log(maxChain(arr));
// 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

大数相加

JavaScript 中的数字按照 IEEE 754 的标准,使用 64 位双精度浮点型来表示。其中符号位 S,指数位 E,尾数位 M 分别占了 1,11,52 位,并且在 ES5 规范 中指出了指数位 E 的取值范围是 [-1074, 971]。

64bit

计算机的二进制实现和位数限制有些数无法有限表示。就像一些无理数不能有限表示,如圆周率 3.1415926...,1.3333... 等。

输入十进制数,转化为二进制运算过后再转化回来,在转化过程中自然会有损失

0.5(十进制) = 0.1(二进制),因为 2^-1 是 0.5。
0.25(十进制) = 0.01(二进制),因为 2^-2 是 0.25。
0.1、0.2 表示不出就只能找个最接近的近似值来代表。
0.1 >> 0.0001 1001 1001 1001…(1001 无限循环)
0.2 >> 0.0011 0011 0011 0011…(0011 无限循环)

大整数的精度丢失和浮点数本质上是一样的,尾数位最大是 52 位,
因此 JS 中能精准表示的最大整数是 Math.pow(2, 53),十进制即 9007199254740992。

大于 9007199254740992 的可能会丢失精度

9007199254740992     >> 10000000000000...000 // 共计 53 个 0
9007199254740992 + 1 >> 10000000000000...001 // 中间 52 个 0
9007199254740992 + 2 >> 10000000000000...010 // 中间 51 个 0
实际上

9007199254740992 + 1 // 丢失
9007199254740992 + 2 // 未丢失
9007199254740992 + 3 // 丢失
9007199254740992 + 4 // 未丢失
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  • 整数
var a = "9007199254740991";
var b = "1234567899999999999";

function addUseFor(a, b) {
    var sum = "";
    var yu = 0;
    var maxLength = Math.max(a.length, b.length);
    //用0去补齐长度
    a = a.padStart(maxLength, 0); //"0009007199254740991"
    b = b.padStart(maxLength, 0); //"1234567899999999999"
    for (let i = 1; i <= maxLength; i++) {
        var aIndex = parseInt(a[a.length - i]);
        var bIndex = parseInt(b[b.length - i]);
        var tmpSum = aIndex + bIndex + yu;
        yu = 0;
        if (tmpSum >= 10) {
            yu = 1;
            tmpSum = tmpSum - 10;
        }
        sum = tmpSum + sum;
    }
    return sum;
}

function addUseWhile(a, b) {
    var sum = "";
    var yu = 0;
    var index = 1;
    var maxLength = Math.max(a.length, b.length);
    //用0去补齐长度
    a = a.padStart(maxLength, 0); //"0009007199254740991"
    b = b.padStart(maxLength, 0); //"1234567899999999999"
    while (index <= maxLength) {
        var aIndex = parseInt(a[a.length - index]);
        var bIndex = parseInt(b[b.length - index]);
        var tmpSum = aIndex + bIndex + yu;
        yu = 0;
        if (tmpSum >= 10) {
            yu = 1;
            tmpSum = tmpSum - 10;
        }
        sum = tmpSum + sum;
        index++;
    }
    return sum;
}

function add2(a, b) {
    //取两个数字的最大长度
    let maxLength = Math.max(a.length, b.length);
    //用0去补齐长度
    a = a.padStart(maxLength, 0); //"0009007199254740991"
    b = b.padStart(maxLength, 0); //"1234567899999999999"
    //定义加法过程中需要用到的变量
    let t = 0;
    let f = 0; //"进位"
    let sum = "";
    for (let i = maxLength - 1; i >= 0; i--) {
        t = parseInt(a[i]) + parseInt(b[i]) + f;
        f = Math.floor(t / 10);
        sum = (t % 10) + sum;
    }
    if (f == 1) {
        sum = "1" + sum;
    }
    return sum;
}
console.log("先测试正确性:");
console.log(addUseWhile(a, b));
console.log(addUseFor(a, b));
console.log(add2(a, b));
console.log("再测试计算性能:");
var Benchmark = require("benchmark");
new Benchmark.Suite()
    .add("addUseWhile", function () {
        addUseWhile(a, b);
    })
    .add("addUseFor", function () {
        addUseFor(a, b);
    })
    .add("add2", function () {
        add2(a, b);
    })
    // add listeners
    .on("cycle", function (event) {
        console.log(String(event.target));
    })
    .on("complete", function () {
        console.log("最快的算法是:" + this.filter("fastest").map("name"));
    })
    .run({ async: true });

/**
先测试正确性:
1243575099254740990
1243575099254740990
1243575099254740990
再测试计算性能:
addUseWhile x 1,840,974 ops/sec ±0.51% (87 runs sampled)
addUseFor x 1,864,282 ops/sec ±0.41% (88 runs sampled)
add2 x 1,628,659 ops/sec ±0.52% (84 runs sampled)
最快的算法是:addUseFor
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

大数(含小数位)

// 借助整数相加 addInt, 小数相加 addFloat
// 简单思路实现,不做验证和优化
function add(a, b) {
    var a_int = a.split(".")[0];
    var a_float = a.split(".")[1];
    var b_int = b.split(".")[0];
    var b_float = b.split(".")[1];
    // 整数部分
    var _int = addInt(a_int, b_int);
    // 小数部分
    var _float = addFloat(a_float, b_float);
    // 小数部分有没有进位?
    if (_float.length > Math.max(a_float.length, b_float.length)) {
        _float = _float.slice(1, _float.length + 1);
        _int = add(_int, "1");
    }
    return _int + "." + _float;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18