大数相加与相乘

问题

JavaScript 的 Number 类型最大安全整数是 2^53 - 1，超过这个范围会丢失精度。如何实现任意大数的加法和乘法？

// Number 精度问题
console.log(9999999999999999 + 1); // 10000000000000000 ❌
console.log(BigInt('9999999999999999') + 1n); // 10000000000000000n ✅

// 面试要求：不用 BigInt，用字符串模拟

解答

大数相加

function addStrings(num1, num2) {
  let i = num1.length - 1;
  let j = num2.length - 1;
  let carry = 0; // 进位
  let result = '';

  // 从末位开始逐位相加
  while (i >= 0 || j >= 0 || carry) {
    const n1 = i >= 0 ? Number(num1[i]) : 0;
    const n2 = j >= 0 ? Number(num2[j]) : 0;
    const sum = n1 + n2 + carry;

    result = (sum % 10) + result; // 当前位
    carry = Math.floor(sum / 10); // 进位

    i--;
    j--;
  }

  return result;
}

// 测试
console.log(addStrings('999999999999999999', '1'));
// '1000000000000000000'

console.log(addStrings('123', '456'));
// '579'

大数相乘

function multiplyStrings(num1, num2) {
  // 处理乘以 0 的情况
  if (num1 === '0' || num2 === '0') return '0';

  const m = num1.length;
  const n = num2.length;
  // 结果最多 m + n 位
  const result = new Array(m + n).fill(0);

  // 从末位开始，逐位相乘
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      const mul = Number(num1[i]) * Number(num2[j]);
      // p1 是高位，p2 是低位
      const p1 = i + j;
      const p2 = i + j + 1;

      // 加上之前的进位
      const sum = mul + result[p2];

      result[p2] = sum % 10; // 当前位
      result[p1] += Math.floor(sum / 10); // 进位累加到高位
    }
  }

  // 去掉前导零
  const str = result.join('');
  return str.replace(/^0+/, '') || '0';
}

// 测试
console.log(multiplyStrings('123', '456'));
// '56088'

console.log(multiplyStrings('999999999999', '999999999999'));
// '999999999998000000000001'

大数相减（补充）

function subtractStrings(num1, num2) {
  // 假设 num1 >= num2，都是正整数
  let i = num1.length - 1;
  let j = num2.length - 1;
  let borrow = 0; // 借位
  let result = '';

  while (i >= 0) {
    const n1 = Number(num1[i]);
    const n2 = j >= 0 ? Number(num2[j]) : 0;
    let diff = n1 - n2 - borrow;

    if (diff < 0) {
      diff += 10;
      borrow = 1;
    } else {
      borrow = 0;
    }

    result = diff + result;
    i--;
    j--;
  }

  // 去掉前导零
  return result.replace(/^0+/, '') || '0';
}

// 测试
console.log(subtractStrings('1000', '1')); // '999'
console.log(subtractStrings('123', '23')); // '100'

关键点

• 从低位到高位：模拟手算，从个位开始处理
• 进位/借位处理：加法用 Math.floor(sum / 10)，减法需要向高位借 10
• 乘法位置公式：num1[i] * num2[j] 的结果影响 result[i+j] 和 result[i+j+1]
• 边界处理：前导零、乘以 0、两数长度不等
• 时间复杂度：加法 O(max(m,n))，乘法 O(m×n)