大数相加

问题

实现两个大整数相加。由于 JavaScript 的 Number 类型只能安全表示 $-2^{53}+1$ 到 $2^{53}-1$ 之间的整数，超出范围会丢失精度。

答案

大数相加的核心思路是将数字转为字符串，模拟竖式加法从低位到高位逐位相加。

---

为什么需要大数运算？

// JavaScript 精度问题
console.log(9007199254740992 + 1); // 9007199254740992 ❌ 应该是 9007199254740993
console.log(Number.MAX_SAFE_INTEGER); // 9007199254740991

// 大数相加
const a = '9007199254740992';
const b = '1';
console.log(addBigNumbers(a, b)); // '9007199254740993' ✅

---

基础实现

function addBigNumbers(a: string, b: string): string {
  let i = a.length - 1;
  let j = b.length - 1;
  let carry = 0;
  let result = '';

  while (i >= 0 || j >= 0 || carry > 0) {
    const digitA = i >= 0 ? parseInt(a[i], 10) : 0;
    const digitB = j >= 0 ? parseInt(b[j], 10) : 0;

    const sum = digitA + digitB + carry;
    result = (sum % 10) + result;
    carry = Math.floor(sum / 10);

    i--;
    j--;
  }

  return result;
}

// 测试
console.log(addBigNumbers('123', '456'));                    // '579'
console.log(addBigNumbers('999', '1'));                      // '1000'
console.log(addBigNumbers('12345678901234567890', '1'));     // '12345678901234567891'

---

优化版本

使用数组更高效

function addBigNumbersArray(a: string, b: string): string {
  const arrA = a.split('').map(Number).reverse();
  const arrB = b.split('').map(Number).reverse();
  const result: number[] = [];
  let carry = 0;

  const maxLen = Math.max(arrA.length, arrB.length);

  for (let i = 0; i < maxLen || carry > 0; i++) {
    const sum = (arrA[i] || 0) + (arrB[i] || 0) + carry;
    result.push(sum % 10);
    carry = Math.floor(sum / 10);
  }

  return result.reverse().join('');
}

处理前导零和符号

function addBigNumbersFull(a: string, b: string): string {
  // 处理空值
  if (!a || a === '0') return b || '0';
  if (!b || b === '0') return a;

  // 处理负数
  const isNegativeA = a.startsWith('-');
  const isNegativeB = b.startsWith('-');

  if (isNegativeA && isNegativeB) {
    // 两个负数：-a + -b = -(a + b)
    return '-' + addBigNumbers(a.slice(1), b.slice(1));
  }

  if (isNegativeA) {
    // a 为负：-a + b = b - a
    return subtractBigNumbers(b, a.slice(1));
  }

  if (isNegativeB) {
    // b 为负：a + -b = a - b
    return subtractBigNumbers(a, b.slice(1));
  }

  // 移除前导零
  a = a.replace(/^0+/, '') || '0';
  b = b.replace(/^0+/, '') || '0';

  return addBigNumbers(a, b);
}

---

大数减法

function subtractBigNumbers(a: string, b: string): string {
  // 比较大小，确保大数减小数
  if (isSmaller(a, b)) {
    return '-' + subtractBigNumbers(b, a);
  }

  let i = a.length - 1;
  let j = b.length - 1;
  let borrow = 0;
  let result = '';

  while (i >= 0) {
    let diff = parseInt(a[i], 10) - borrow - (j >= 0 ? parseInt(b[j], 10) : 0);

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

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

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

function isSmaller(a: string, b: string): boolean {
  if (a.length !== b.length) {
    return a.length < b.length;
  }
  return a < b;
}

// 测试
console.log(subtractBigNumbers('1000', '1'));    // '999'
console.log(subtractBigNumbers('123', '456'));   // '-333'
console.log(subtractBigNumbers('456', '123'));   // '333'

---

大数乘法

function multiplyBigNumbers(a: string, b: string): string {
  if (a === '0' || b === '0') return '0';

  const m = a.length;
  const n = b.length;
  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 = parseInt(a[i], 10) * parseInt(b[j], 10);
      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('').replace(/^0+/, '');
  return str || '0';
}

// 测试
console.log(multiplyBigNumbers('123', '456'));  // '56088'
console.log(multiplyBigNumbers('99', '99'));    // '9801'

---

大数除法

function divideBigNumbers(a: string, b: string): { quotient: string; remainder: string } {
  if (b === '0') throw new Error('Division by zero');
  if (isSmaller(a, b)) return { quotient: '0', remainder: a };

  let quotient = '';
  let current = '';

  for (const digit of a) {
    current += digit;
    current = current.replace(/^0+/, '') || '0';

    let count = 0;
    while (!isSmaller(current, b)) {
      current = subtractBigNumbers(current, b);
      count++;
    }
    quotient += count;
  }

  return {
    quotient: quotient.replace(/^0+/, '') || '0',
    remainder: current,
  };
}

// 测试
console.log(divideBigNumbers('100', '3'));  // { quotient: '33', remainder: '1' }
console.log(divideBigNumbers('123456789', '123'));  // { quotient: '1003713', remainder: '90' }

---

完整大数类

class BigNumber {
  private value: string;
  private negative: boolean;

  constructor(value: string | number) {
    const str = String(value);
    this.negative = str.startsWith('-');
    this.value = (this.negative ? str.slice(1) : str).replace(/^0+/, '') || '0';
  }

  // 加法
  add(other: BigNumber): BigNumber {
    if (this.negative === other.negative) {
      // 同号相加
      const result = this.addStrings(this.value, other.value);
      return new BigNumber(this.negative ? '-' + result : result);
    } else {
      // 异号相减
      const cmp = this.compareAbs(other);
      if (cmp === 0) return new BigNumber('0');
      if (cmp > 0) {
        const result = this.subtractStrings(this.value, other.value);
        return new BigNumber(this.negative ? '-' + result : result);
      } else {
        const result = this.subtractStrings(other.value, this.value);
        return new BigNumber(other.negative ? '-' + result : result);
      }
    }
  }

  // 减法
  subtract(other: BigNumber): BigNumber {
    return this.add(other.negate());
  }

  // 取反
  negate(): BigNumber {
    if (this.value === '0') return new BigNumber('0');
    return new BigNumber(this.negative ? this.value : '-' + this.value);
  }

  // 比较绝对值
  private compareAbs(other: BigNumber): number {
    if (this.value.length !== other.value.length) {
      return this.value.length - other.value.length;
    }
    return this.value.localeCompare(other.value);
  }

  // 字符串加法
  private addStrings(a: string, b: string): string {
    let i = a.length - 1;
    let j = b.length - 1;
    let carry = 0;
    let result = '';

    while (i >= 0 || j >= 0 || carry > 0) {
      const sum = (i >= 0 ? +a[i--] : 0) + (j >= 0 ? +b[j--] : 0) + carry;
      result = (sum % 10) + result;
      carry = Math.floor(sum / 10);
    }

    return result;
  }

  // 字符串减法（a >= b）
  private subtractStrings(a: string, b: string): string {
    let i = a.length - 1;
    let j = b.length - 1;
    let borrow = 0;
    let result = '';

    while (i >= 0) {
      let diff = +a[i--] - borrow - (j >= 0 ? +b[j--] : 0);
      if (diff < 0) {
        diff += 10;
        borrow = 1;
      } else {
        borrow = 0;
      }
      result = diff + result;
    }

    return result.replace(/^0+/, '') || '0';
  }

  toString(): string {
    return (this.negative ? '-' : '') + this.value;
  }
}

// 使用
const a = new BigNumber('12345678901234567890');
const b = new BigNumber('98765432109876543210');
console.log(a.add(b).toString()); // '111111111011111111100'

---

使用 BigInt（ES2020）

// ES2020 原生支持
const bigA = BigInt('9007199254740992');
const bigB = BigInt('1');
console.log((bigA + bigB).toString()); // '9007199254740993'

// 大数运算
const huge = BigInt('12345678901234567890123456789');
console.log((huge * 2n).toString());

// 注意：BigInt 不能和 Number 混用
// bigA + 1; // TypeError

---

常见面试问题

Q1: 为什么不直接用 Number？

答案：

JavaScript 的 Number 使用 IEEE 754 双精度浮点数，只能安全表示 $2^{53}-1$ 以内的整数：

console.log(Number.MAX_SAFE_INTEGER);        // 9007199254740991
console.log(9007199254740992 === 9007199254740993); // true ❌

超出安全范围会丢失精度，必须用字符串或 BigInt 处理。

Q2: 时间复杂度是多少？

答案：

操作	时间复杂度
加法	O(max(m, n))
减法	O(max(m, n))
乘法	O(m × n)
除法	O(m × n)

其中 m、n 为两个数字的位数。

Q3: 如何处理小数？

答案：

function addBigDecimals(a: string, b: string): string {
  // 分离整数和小数部分
  const [intA, decA = ''] = a.split('.');
  const [intB, decB = ''] = b.split('.');

  // 对齐小数位数
  const maxDecLen = Math.max(decA.length, decB.length);
  const paddedDecA = decA.padEnd(maxDecLen, '0');
  const paddedDecB = decB.padEnd(maxDecLen, '0');

  // 作为整数相加
  const fullA = intA + paddedDecA;
  const fullB = intB + paddedDecB;
  const sum = addBigNumbers(fullA, fullB);

  // 插入小数点
  if (maxDecLen === 0) return sum;

  const intPart = sum.slice(0, -maxDecLen) || '0';
  const decPart = sum.slice(-maxDecLen).replace(/0+$/, '');

  return decPart ? `${intPart}.${decPart}` : intPart;
}

console.log(addBigDecimals('1.5', '2.7'));     // '4.2'
console.log(addBigDecimals('99.99', '0.01')); // '100'

相关链接

• BigInt - MDN
• Add Strings - LeetCode
• Multiply Strings - LeetCode