前言

這是一篇偏綜合性的總結(jié)，根據(jù)筆者的 routine 整理好的，并對(duì)代碼進(jìn)行了改進(jìn)。以下內(nèi)容出處均已在 參考資料 中列出，如有侵權(quán)，聯(lián)系筆者刪除。

思維導(dǎo)圖

[圖片上傳失敗...(image-29c229-1586171075473)]

<a name="9hn0G"></a>

前置知識(shí)

<a name="oM17p"></a>

本質(zhì)原因

計(jì)算機(jī)是二進(jìn)制的，無法直接表示正負(fù)數(shù)，另外在計(jì)算機(jī)內(nèi)部直接實(shí)現(xiàn)減法，也會(huì)影響計(jì)算機(jī)效率，所以人們希望要找到一種既能使用二進(jìn)制表示10進(jìn)制正負(fù)數(shù)的編碼格式，同時(shí)這種編碼格式又能滿足將減法轉(zhuǎn)換成加法進(jìn)行運(yùn)算。<br />

<a name="crcuw"></a>

原碼、反碼和補(bǔ)碼

<a name="FHWGr"></a>

原碼

image.png

<a name="nx3FJ"></a>

反碼

image.png

<a name="Q1D58"></a>

補(bǔ)碼

image.png

<a name="YIcky"></a>

總結(jié)

要想弄清楚補(bǔ)碼，必須要弄清楚補(bǔ)碼要解決的問題，計(jì)算機(jī)是二進(jìn)制的，無法直接表示正負(fù)數(shù)，另外在計(jì)算機(jī)內(nèi)部直接實(shí)現(xiàn)減法，也會(huì)影響計(jì)算機(jī)效率，所以人們希望要找到一種既能使用二進(jìn)制表示10進(jìn)制正負(fù)數(shù)的編碼格式，同時(shí)這種編碼格式又能滿足將減法轉(zhuǎn)換成加法進(jìn)行運(yùn)算，同時(shí)滿足這兩個(gè)條件有反碼和補(bǔ)碼，但由于反碼中的0有兩個(gè)編碼格式，另外反碼加法運(yùn)算也比較復(fù)雜，慢慢地反碼被淘汰了。補(bǔ)碼剛好解決了反碼的兩個(gè)缺點(diǎn)，所以補(bǔ)碼成了現(xiàn)代計(jì)算機(jī)的通用編碼。<br />

<a name="Bsieu"></a>

IEEE 754標(biāo)準(zhǔn)

<a name="wekxi"></a>

背景

隨著技術(shù)的更新，在1978年的時(shí)候，Intel公司推出了首枚16bit微處理器(CPU)8086。這臺(tái)x86的老祖宗雖然自身無法處理小數(shù)的運(yùn)算，但是在編譯器層面可以通過用整數(shù)指令模擬出小數(shù)的運(yùn)算，不過這種運(yùn)算的方式效率是非常低的。<br />
<br />為了解決這類問題，1980年Intel公司推出了首款x87浮點(diǎn)協(xié)處理器運(yùn)算單元(FPU)8087，通過主板上額外的協(xié)處理器插槽，安裝后不僅可以解決小數(shù)的運(yùn)算問題，并且對(duì)于不同的應(yīng)用，性能提升了20%~500%。<br />
<br />對(duì)于計(jì)算機(jī)發(fā)展來說，8087是款非常棒的FPU，但是它的意義真正體現(xiàn)在這款FPU的設(shè)計(jì)師之一的William Kahan教授設(shè)計(jì)了IEEE-754標(biāo)準(zhǔn)的雛形，而正是因?yàn)檫@套標(biāo)準(zhǔn)，我們計(jì)算機(jī)才能精準(zhǔn)的處理小數(shù)。<br />
<br />1985年時(shí)，IEEE推出了IEEE 754-1985標(biāo)準(zhǔn)，隨著大佬們的努力，IEEE還推出了目前的版本——IEEE 754-2008。<br />
<br />而我們使用的高級(jí)語言中浮點(diǎn)數(shù)的運(yùn)算，如C、C++、JavaScript、Java都是基于這個(gè)標(biāo)準(zhǔn)而定。<br />

<a name="MzWgK"></a>

概念

image.png

image.png

image.png

image.png

<a name="RH8nK"></a>

概念

JavaScript的數(shù)字類型的本質(zhì)就是一個(gè)基于 IEEE 754 標(biāo)準(zhǔn)的雙精度 64 位的浮點(diǎn)數(shù)。
<a name="yGXlK"></a>

小數(shù)運(yùn)算（為什么0.2 + 0.1 !== 0.3？）

<a name="I3R1e"></a>

概述

1. 0.1 和 0.2 按照 IEEE 754 存儲(chǔ)后都有精度損失
2. 運(yùn)算后進(jìn)行規(guī)格化時(shí)的舍入操作也有精度損失

**
<a name="A9NP0"></a>

詳解

關(guān)于浮點(diǎn)數(shù)的運(yùn)算，一般由以下五個(gè)步驟完成：對(duì)階、尾數(shù)運(yùn)算、規(guī)格化、舍入處理、溢出判斷。<br />

image.png

解決方案

number-precision<br />全面總結(jié) JS 中浮點(diǎn)數(shù)運(yùn)算問題 - 掘金
<a name="sXlqN"></a>

大數(shù)運(yùn)算如何處理？

<a name="uyCRz"></a>

現(xiàn)成方案

1.bignumber.js<br />2.true-json-bigint.js<br />3.BigInt - JavaScript | MDN<br />

image.png

大數(shù)運(yùn)算

<a name="fdEoq"></a>

核心思想

既然數(shù)字類型會(huì)有精度問題，那就統(tǒng)統(tǒng)轉(zhuǎn)用字符串來處理。
<a name="KMWlE"></a>

大數(shù)相加

<br />普通版本

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
function add(a, b) {
  // 首先檢查傳來的大數(shù)是否是字符串類型，如果傳Number類型的大數(shù)，在傳入的時(shí)候已經(jīng)丟失精度了，
  // 就如 如果傳入11111111111111111，處理的時(shí)候已經(jīng)是丟失精度的11111111111111112了，則需要傳入
  // 字符串類型的數(shù)字 '11111111111111111'
  const checkNum = num => typeof num === "string" && !isNaN(Number(num))
  // 格式化數(shù)字
  const formatNum = num => (isNaN(+num) ? 0 : +num)

  if (!checkNum(a) || !checkNum(b)) {
    throw new TypeError("Big Number Type Error")
  }
  const result = []

  a = a.split("").reverse()
  b = b.split("").reverse()
  const length = Math.max(a.length, b.length)

  let carry = 0
  
  // 以較長(zhǎng)的數(shù)字為基準(zhǔn)進(jìn)行從前往后逐個(gè)加和，為避免兩個(gè)數(shù)相加最高位進(jìn)位后，導(dǎo)
  // 致結(jié)果長(zhǎng)度大于兩個(gè)數(shù)字中的長(zhǎng)度，for循環(huán)加和長(zhǎng)度為最長(zhǎng)數(shù)字長(zhǎng)度加一
  for (let i = 0; i <= length; i++) {
    const tempResult = formatNum(a[i]) + formatNum(b[i]) + carry
    result[i] = tempResult % 10
    
    // 當(dāng)加和的數(shù)字大于10的情況下，進(jìn)行進(jìn)位操作，將要進(jìn)位的數(shù)字賦值給temp，在下一輪使用
    carry = Math.trunc(tempResult / 10)
  }
  
  // 計(jì)算完成，反轉(zhuǎn)回來
  result.reverse()
  
  // 將數(shù)組for中多加的一位進(jìn)行處理，如果最高位沒有進(jìn)位則結(jié)果第一個(gè)數(shù)位0，
  // 結(jié)果第一個(gè)數(shù)位1，則發(fā)生了進(jìn)位。 如99+3，最大數(shù)字長(zhǎng)度位2,結(jié)果數(shù)長(zhǎng)度位3
  // 此時(shí)結(jié)果的第一位為1，發(fā)生了進(jìn)位，第一位保留，如果是2+94，第一位為0，則不保留第一位
  return result.join('').replace(/^0+/, "")
}

<br />奇技淫巧版

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
function add(a, b) {
  const checkNum = num => typeof num === "string" && !isNaN(Number(num))

  if (!checkNum(a) || !checkNum(b)) {
    throw new TypeError("Big Number Type Error")
  }

  let result = ""

  let c = 0
  a = a.split("")
  b = b.split("")

  while (a.length || b.length || c) {
    
    // ~取反操作符，~0 === -1, ~~0 === 0, ~~null === 0, ~~undefined === 0, ~~'0' === 0
        // 用+也能實(shí)現(xiàn)字符轉(zhuǎn)成數(shù)字，不過~~能處理null的情況
    c = ~~a.pop() + ~~b.pop() + c
    result += c % 10
    
    // c>0會(huì)返回一個(gè)布爾值，布爾值轉(zhuǎn)換成數(shù)字的時(shí)候true為1，false為0
    c = c > 9
  }

  return result.replace(/^0+/, "")
}

<br />優(yōu)化版

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
function add(a, b) {
  const checkNum = num => typeof num === "string" && !isNaN(Number(num))

  if (!checkNum(a) || !checkNum(b)) {
    throw new TypeError("Big Number Type Error")
  }
  
  // 主要思想是分開一段段加，這樣既能保證精度且不溢出，也能提高速度
    // 如果索引超范圍，或者長(zhǎng)度小于1那么返回空字符串

  const MAX_PERCISION = Number.MAX_SAFE_INTEGER.toString().length - 1
  const arr = []

  while (a.length || b.length) {
    arr.push(
      parseInt(a.substring(a.length - MAX_PERCISION) || 0, 10) +
      parseInt(b.substring(b.length - MAX_PERCISION) || 0, 10)
    )
    a = a.substring(0, a.length - MAX_PERCISION)
    b = b.substring(0, b.length - MAX_PERCISION)
  }

  let carry = 0
  let result = ""

  while (arr.length) {
    const temp = (arr.shift() + carry).toString()
    result = temp.substring(temp.length - MAX_PERCISION) + result
    carry = parseInt(
      temp.substring(0, temp.length - MAX_PERCISION) || 0,
      10
    )
  }

  return result
}

// 簡(jiǎn)化 =>

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
function add(a, b) {
  const checkNum = num => typeof num === "string" && !isNaN(Number(num))

  if (!checkNum(a) || !checkNum(b)) {
    throw new TypeError("Big Number Type Error")
  }

  const MAX_PERCISION = Number.MAX_SAFE_INTEGER.toString().length - 1

  let result = ""
  let carry = 0

  while (a.length || b.length) {
    const temp = (
      parseInt(a.substring(a.length - MAX_PERCISION) || 0, 10) +
      parseInt(b.substring(b.length - MAX_PERCISION) || 0, 10) +
      carry
    ).toString()
    result = temp.substring(temp.length - MAX_PERCISION) + result
    carry = parseInt(
      temp.substring(0, temp.length - MAX_PERCISION) || 0,
      10
    )

    a = a.substring(0, a.length - MAX_PERCISION)
    b = b.substring(0, b.length - MAX_PERCISION)
  }

  return result
}

<a name="sWeXq"></a>

大數(shù)相減

<br />奇技淫巧版

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
function minus(a, b) {
  const checkNum = num => typeof num === "string" && !isNaN(Number(num))

  if (!checkNum(a) || !checkNum(b)) {
    throw new TypeError("Big Number Type Error")
  }

  while (a.length < b.length) {
    a = "0" + a
  }
  while (b.length < a.length) {
    b = "0" + b
  }

  let result = ""
  let borrow = false

  a = a.split("")
  b = b.split("")

  while (a.length) {
    const minuend = ~~a.pop()
    const subtrahend = ~~b.pop() + borrow

    if (minuend >= subtrahend) {
      borrow = minuend - subtrahend
      result = borrow + result
      borrow = false
    } else {
      borrow = minuend + 10 - subtrahend
      result = borrow + result
      borrow = true
    }
    //判斷最高位有無借位，若有借位，則說明結(jié)果為負(fù)數(shù)
    if (a.length === 0 && borrow) {
      result = "-" + result
    }
  }

  result = result.replace(/^0+/, "")

  //判斷最后的結(jié)果是否為0
  if (result === "") {
    result = 0
  }
  return result
}

<a name="KR1tt"></a>

大數(shù)相乘

目前大數(shù)乘法算法主要有以下幾種思路：

1. 模擬小學(xué)乘法：最簡(jiǎn)單的乘法豎式手算的累加型；
2. 分治乘法：最簡(jiǎn)單的是Karatsuba乘法，一般化以后有Toom-Cook乘法；
3. 快速傅里葉變換FFT：（為了避免精度問題，可以改用快速數(shù)論變換FNTT），時(shí)間復(fù)雜度O(N lgN lglgN)。具體可參照Sch?nhage–Strassen algorithm；
4. 中國(guó)剩余定理：把每個(gè)數(shù)分解到一些互素的模上，然后每個(gè)同余方程對(duì)應(yīng)乘起來就行；
5. Furer’s algorithm：在漸進(jìn)意義上FNTT還快的算法。不過好像不太實(shí)用，本文就不作介紹了。大家可以參考維基百科Fürer’s algorithm

<br />模擬小學(xué)乘法版

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
function multiply(a, b) {
  const cn = a.length + b.length
  const c = new Array(cn).fill(0)
  /****
         * 兩兩相乘，并放進(jìn)不同的格子里，如果里面有東西，則相加
         * 0
         *   8
         *     10
         *     4
         *       5
         */
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < b.length; j++) {
      c[i + j + 1] += Number(a[i]) * Number(b[j])
    }
  }
  // 處理進(jìn)位
  for (let i = cn - 1; i >= 0; i--) {
    const carry = Math.trunc(c[i] / 10)
    if (carry) {
      c[i - 1] += carry
    }
    c[i] = c[i] % 10
  }
  while (c[0] === 0) {
    c.shift()
  }
  //處理最前面的零
  return c.join("") || "0"
}

<br />利用下標(biāo)取巧版

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
function multiply(num1, num2) {
    const checkNum = num => typeof num === "string" && !isNaN(Number(num))

  if (!checkNum(a) || !checkNum(b)) {
    throw new TypeError("Big Number Type Error")
  }
 
  let len1 = a.length,
      len2 = b.length
  let ans = []

  //這里倒過來遍歷很妙,不需要處理進(jìn)位了
  for (let i = len1 - 1; i >= 0; i--) {
    for (let j = len2 - 1; j >= 0; j--) {
      let index1 = i + j,
          index2 = i + j + 1
      let mul = a[i] * b[j] + (ans[index2] || 0)
      ans[index1] = Math.floor(mul / 10) + (ans[index1] || 0)
      ans[index2] = mul % 10
    }
  }

  //去掉前置0
  let result = ans.join("").replace(/^0+/, "")

  //不要轉(zhuǎn)成數(shù)字判斷，否則可能會(huì)超精度！
  return !result ? "0" : result
}

<a name="haUnb"></a>

大數(shù)相除

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
function divide(a, b) {
  const checkNum = num => typeof num === "string" && !isNaN(Number(num))

  if (!checkNum(a) || !checkNum(b)) {
    throw new TypeError("Big Number Type Error")
  }
  
  const alen = a.length
  const blen = b.length
  let quotient = 0
  let remainder = 0
  const result = []
  let temp = 0
  for (let i = 0; i < alen; i++) {
    temp = remainder * 10 + parseInt(a[i])
    if (temp < b) {
      remainder = temp
      result.push(0)
    } else {
      quotient = parseInt(temp / b)
      remainder = temp % b
      result.push(quotient)
    }
  }
  return [result.join("").replace(/\b(0+)/gi, ""), remainder] //結(jié)果返回[商，余數(shù)]
}

<a name="QvjwM"></a>

大數(shù)階乘

function fact(num) {
  let result = 1
  for(let i=1; i<=num; i++){
    result = result * i
  }
  return result
}

// => 

function fact(num) {
  const checkNum = num => typeof num === "string" && !isNaN(Number(num))

  if (!checkNum(num)) {
    throw new TypeError("Big Number Type Error")
  }
  
  let result = "1"
  for (let i = "1"; lte(i, num); i = add(i, "1")) {
    result = multiply(result, i)
  }
  return result
}

function lte(num1, num2) {
  if (num1.length < num2.length) {
    return true
  } else if (num1.length === num2.length) {
    return num1 <= num2
  } else {
    return false
  }
}

<a name="bBxat"></a>

參考資料

1. 原碼、反碼、補(bǔ)碼的產(chǎn)生、應(yīng)用以及優(yōu)缺點(diǎn)有哪些？
2. 原碼, 反碼, 補(bǔ)碼 詳解 - ziqiu.zhang - 博客園
3. IEEE-754標(biāo)準(zhǔn)與浮點(diǎn)數(shù)運(yùn)算C/C++馬駿超的博客-CSDN博客
4. JavaScript 深入之浮點(diǎn)數(shù)精度 - 掘金
5. 為什么不要在 JavaScript 中使用位操作符？ | 咀嚼之味
6. [每日一題] JavaScript面試之“大數(shù)相加”運(yùn)算 - 云+社區(qū) - 騰訊云
7. A comparison of BigNumber libraries in JavaScript
8. 談?wù)凧S中的大數(shù)運(yùn)算 | 前端腳印
9. 有趣的大數(shù)運(yùn)算
10. JavaScript實(shí)現(xiàn)大整數(shù)減法_JavaScript_xiaoxiaoyoumeng的博客-CSDN博客
11. js實(shí)現(xiàn)大數(shù)相乘 - 個(gè)人文章 - SegmentFault 思否
12. [leetcode] 大數(shù)乘法
13. 【算法】大數(shù)乘法問題及其高效算法 | iTimeTraveler