BFE.devAI解答 - JavaScript 代码题
115. 实现大整数除法(BigInt)

解题思路：

大整数除法的过程类似手算除法，从被除数的最高位开始，依次做减法，求出商的当前位数字，再将余数除以除数作为下一步的被除数。

但是由于 JavaScript 对大整数的处理存在精度问题，因此我们可以采用字符串的形式来处理大整数。具体来说，我们可以采用如下的做法：

1. 先将两个大整数转换为相应的数字数组，方便数位的访问和运算。
2. 利用比较简单的小学奥数方法，从高位到低位模拟手算除法，依次求出商的每一位数字，并计算当前的余数。
   • 如果结果为负数，则商的当前位减1，余数加上除数的绝对值。
3. 最后得到的商的数字数组除以 10 就是最终的结果。

代码如下：

function divide(str1, str2) {
  // 将字符串反转，便于从高位到低位计算
  const num1 = str1.split('').reverse().map(x => +x);
  const num2 = str2.split('').reverse().map(x => +x);

  // 判断正负号
  const sign1 = num1[num1.length - 1] < 0 ? -1 : 1;
  const sign2 = num2[num2.length - 1] < 0 ? -1 : 1;
  const sign = sign1 * sign2;

  // 去掉正负号，转成绝对值
  num1.pop();
  num2.pop();
  const len1 = num1.length, len2 = num2.length;

  // 特判除数为 0 的情况
  if (len2 === 0) {
    throw new Error('除数不能为 0');
  }

  // 特判被除数为零的情况
  if (len1 === 0 || (len1 === 1 && num1[0] === 0)) {
    return '0';
  }

  // 特判两数相等的情况
  if (len1 === len2 && num1.every((digit, i) => digit === num2[i])) {
    return sign > 0 ? '1' : '-1';
  }

  // 将数字数组倒序，方便从高位到低位计算
  num1.reverse();
  num2.reverse();

  const result = []; // 存放商的每一位数字
  let r = 0; // 当前的余数

  // 从高位到低位模拟手算除法
  for (let i = len1 - 1; i >= 0; i--) {
    r = r * 10 + num1[i]; // 加上上一位剩下来的余数
    let q = Math.floor(r / num2[0]); // 计算商的当前位

    // 如果结果为负数，则商的当前位减1，余数加上除数的绝对值
    if (q < 0) {
      q -= 1;
      r += Math.abs(num2[0]);
    }

    result.push(Math.abs(q));
    r %= num2[0];
  }

  // 将商的数字数组倒序，除以10，转成字符串
  const quotient = result.reverse().reduce((str, digit) => str + digit, '') || '0';
  return sign > 0 ? quotient : '-' + quotient;
}

由于 JavaScript 对 BigInt 的支持还不够完善，因此在实现时使用了数字数组来处理大整数。例如，对于大整数 '1123456787654323456789'，我们把它转换成数字数组 [9, 8, 7, 6, 5, 4, 3, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 1, 1]，其中数组的第一项表示个位，最后一项表示最高位。这样我们就可以方便地从高位到低位访问和计算这个数了。

另外，我们在处理负数时，需要特判商的当前位小于等于 0 的情况。此时我们需要将商的当前位减 1，余数加上除数的绝对值。例如，在上面的例子中，当计算 r / num2[0] < 0 时，我们需要把商的当前位 q 减去 1，余数加上除数的绝对值 |num2[0]|。这是因为在手算除法中，计算商的当前位时是采用除数与被除数的高位项相除的方式，即如果 a >= b，则当前位的商为 $a/b$ 的整数部分。而在 JavaScript 中，整数除法采用的是取商向 0 取整的方式，即 $\lfloor a/b\rfloor$，因此需要特判这种情况。这里的实现方式非常简单，只需要检查商 q 是否小于等于 0 即可，如果是，则将其减 1，余数加上除数的绝对值即可。

时间复杂度：$O(n^2)$，其中 $n$ 为两个大整数的位数之和。具体来说，我们需要对每一位做除法，对于每个除法，都需要做一次减法和一次求商，因此总时间复杂度为 $O(n^2)$。

空间复杂度：$O(n)$，其中 $n$ 为两个大整数的位数之和。使用数字数组存储数位和结果可能需要的额外空间为 $O(n)$。