面试官：怎么求斐波那契数列的第 9292 项？

模拟一道面试题。

面试官：怎么求斐波那契数列的第 9292 项？

初看题目，求斐波那契数列啊，这谁不会？但是要求的是第 9292 项，你心里想了一下，这个数肯定很大，结果会溢出的。但这在面试，总不能不写吧，不然让面试官以为你不会写。毕竟只要不写递归，都能算出来，求 9292 项，也就迭代计算几千次。于是你写出了以下代码：

function Fib(n) {
  if (n < 2) return n
  let fib = [0, 1]
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2]
  }
  return fib[n]
}

console.log(Fib(9292))

结果一跑，不出所料，输出结果是 Infinity。JS 中整数超过其最大可表示的数字（Number.MAX_VALUE）之后，就会变为 Infinity。

继续思考，面试官绝不会想要这样的结果。你心中一想，有没有可能是要求取模之后的值，很多算法题中都要求结果 mod(1e9+7)，有了，每次计算和的时候都对结果去取一次模！

function Fib(n) {
  if (n < 2) return n
  let fib = [0, 1]
  for (let i = 2; i <= n; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % (1e9 + 7)
  }
  return fib[n]
}

console.log(Fib(9292))

运行和，上述代码输出了 295902189，好，这下稳了。你自信的把代码和运行结果交给面试官看。

面试官：你能不取模吗？直接得到完整的结果。

什么？不取模，那整数不是溢出了吗？又想了一会，你想到了 ES2020 中新增的数据类型 BigInt，把运算全部转为 BigInt 之间的运算，不就不会溢出了。一顿操作，你写出了以下代码。

function Fib(n) {
  let fib = [0n, 1n]
  for (let i = 2; i <= n; i++) {
    fib[i] = BigInt(fib[i - 1]) + BigInt(fib[i - 2])
  }
  return fib[n].toString()
}

console.log(Fib(9292))

这次成功输出了完整的结果，即 366...579（中间的数字就不列出了）。肯定考知不知道 BigInt 这个新特性，你满怀信心的交给面试官看。

面试官：结果对了，那你能不能不使用 BigInt 呢？

啊？这次彻底懵了，不允许用 BigInt，那不就是要求手写一个 BigInt。面试进展到这里，你终于懂了，原来面试官要你写的是 BigInt 的原理实现。

不过，我们到不需要实现 BigInt 的所有运算和特性，仅仅限于这题中，我们只要写出 大数加法 即可。让斐波那契数列求和的过程中，结果不溢出。

大数加法的思想也不难，其实就是十进制加法法则： 十进制整数相加，逢 10 进 1。

我们用total 来表示 两个对应位置的数的和再加上来自低位的进位：

let total = carry + +num1[i] + +num2[i]

一个 carray 表示进位，将参与下次一计算。

carry = (total / 10) >>> 0 // 右移取整

而 相加结果的本位 就是 (total % 10)。

整个过程进行循环，循环周期是较长数字字符串（这里用字符串模拟了，也可以用数组模拟）的长度。最终代码和详细注释如下：

// 模拟大数加法
var addBigNumber = function (num1, num2) {
  //哪个小拼接哪个，从而保证两者长度相同
  if (num1.length > num2.length) [num1, num2] = [num2, num1]
  let m = num2.length - num1.length
  for (let i = 0; i < m; i++) {
    num1 = '0' + num1
  }
  let ans = '' // 记录相加结果
  let carry = 0 // 代表进位，初始值 0
  // 从后往前遍历，低位到高位，逢 10 进 1
  for (let i = num2.length - 1; i >= 0; i--) {
    // 总和：没算进位的两字符串对应位置数字与进位相加后的和
    // 这里的 + 是正，字符转数字，作用同 Number()
    let total = carry + +num1[i] + +num2[i]
    // 本位 = 总和 % 10
    ans = (total % 10) + ans
    // 进位 = (总和 / 10) 向下取整，参与下一次运算
    carry = (total / 10) >>> 0
  }
  // 判断最高位是否有进位，有进位则在前面加进位
  if (carry >= 1) {
    ans = carry + ans
  }
  return ans
}

function Fib(n) {
  if (n < 2) return n
  let fib = ['0', '1'] // 全都变为数字字符串
  for (let i = 2; i <= n; i++) {
    // 这里的加法要用大数加法实现
    fib[i] = addBigNumber(fib[i - 1], fib[i - 2])
  }
  return fib[n]
}

console.log(Fib(9292))

以上代码没有使用 BigInt，运行的完整结果是：

最后，你和面试官都欣慰的笑了。原来这题考察的就是 大数加法，也就是模拟 BigInt！现在你也可以试着模拟一下乘法、除法等等。

面试官：怎么求斐波那契数列的第 9292 项？ #

面试官：怎么求斐波那契数列的第 9292 项？