34. 说说你对大数相加的理解？

问题解析

在 JavaScript 中，数字使用 IEEE 754 双精度浮点数表示，最大安全整数为 Number.MAX_SAFE_INTEGER（9007199254740991）。超过这个范围的整数运算会丢失精度。大数相加是解决这个问题的经典算法题。

核心概念

1. JavaScript 数字精度问题

// 最大安全整数
console.log(Number.MAX_SAFE_INTEGER); // 9007199254740991
console.log(Number.MIN_SAFE_INTEGER); // -9007199254740991

// 精度丢失示例
console.log(9007199254740991 + 1); // 9007199254740992
console.log(9007199254740991 + 2); // 9007199254740992 (错误！)

// 更大数字
console.log(12345678901234567890 + 1);
// 12345678901234568000 (精度丢失)

// 浮点数精度问题
console.log(0.1 + 0.2); // 0.30000000000000004

2. 大数表示方法

// 方法1：字符串表示
const bigNum1 = '123456789012345678901234567890';
const bigNum2 = '987654321098765432109876543210';

// 方法2：BigInt（ES2020）
const bigNum3 = 123456789012345678901234567890n;
const bigNum4 = 987654321098765432109876543210n;
console.log(bigNum3 + bigNum4);
// 1111111110111111111011111111100n

// 方法3：数组表示（每一位一个元素）
const bigNum5 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0];

详细解答

1. 字符串逐位相加法

function addStrings(num1, num2) {
  // 确保 num1 是较长的那个
  if (num1.length < num2.length) {
    [num1, num2] = [num2, num1];
  }

  let result = '';
  let carry = 0;
  let i = num1.length - 1;
  let j = num2.length - 1;

  // 从右向左逐位相加
  while (i >= 0 || j >= 0 || carry > 0) {
    const digit1 = i >= 0 ? parseInt(num1[i]) : 0;
    const digit2 = j >= 0 ? parseInt(num2[j]) : 0;

    const sum = digit1 + digit2 + carry;
    result = (sum % 10) + result;
    carry = Math.floor(sum / 10);

    i--;
    j--;
  }

  return result;
}

// 测试
console.log(addStrings('123', '456')); // '579'
console.log(addStrings('999', '1'));   // '1000'
console.log(addStrings('12345678901234567890', '98765432109876543210'));
// '111111111011111111100'

2. 更完善的实现

function bigAdd(a, b) {
  // 处理负数
  if (a[0] === '-' && b[0] === '-') {
    return '-' + bigAdd(a.slice(1), b.slice(1));
  }
  if (a[0] === '-') {
    return bigSubtract(b, a.slice(1));
  }
  if (b[0] === '-') {
    return bigSubtract(a, b.slice(1));
  }

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

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

  while (i >= 0 || j >= 0 || carry) {
    const digit1 = i >= 0 ? a.charCodeAt(i) - 48 : 0; // 比 parseInt 更快
    const digit2 = j >= 0 ? b.charCodeAt(j) - 48 : 0;

    const sum = digit1 + digit2 + carry;
    result = String.fromCharCode((sum % 10) + 48) + result;
    carry = sum >= 10 ? 1 : 0;

    i--;
    j--;
  }

  return result;
}

// 大数减法（辅助函数）
function bigSubtract(a, b) {
  // 确保 a >= b
  if (compareBig(a, b) < 0) {
    return '-' + bigSubtract(b, a);
  }

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

  while (i >= 0) {
    const digit1 = a.charCodeAt(i) - 48 - borrow;
    const digit2 = j >= 0 ? b.charCodeAt(j) - 48 : 0;

    if (digit1 >= digit2) {
      result = String.fromCharCode((digit1 - digit2) + 48) + result;
      borrow = 0;
    } else {
      result = String.fromCharCode((digit1 + 10 - digit2) + 48) + result;
      borrow = 1;
    }

    i--;
    j--;
  }

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

// 比较两个大数
function compareBig(a, b) {
  a = a.replace(/^0+/, '') || '0';
  b = b.replace(/^0+/, '') || '0';

  if (a.length !== b.length) {
    return a.length > b.length ? 1 : -1;
  }

  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      return a[i] > b[i] ? 1 : -1;
    }
  }

  return 0;
}

// 测试
console.log(bigAdd('12345678901234567890', '98765432109876543210'));
console.log(bigAdd('-123', '-456')); // '-579'
console.log(bigAdd('1000', '-1'));   // '999'

深入理解

1. 多位数分组优化

// 将大数分成多组（如每9位一组），减少循环次数
function addStringsOptimized(num1, num2) {
  const CHUNK_SIZE = 9; // 每组9位（小于10^9，避免溢出）
  const BASE = 10 ** CHUNK_SIZE;

  // 补齐长度
  const maxLength = Math.max(num1.length, num2.length);
  const paddedLength = Math.ceil(maxLength / CHUNK_SIZE) * CHUNK_SIZE;
  num1 = num1.padStart(paddedLength, '0');
  num2 = num2.padStart(paddedLength, '0');

  let result = '';
  let carry = 0;

  // 从右向左按组处理
  for (let i = paddedLength - CHUNK_SIZE; i >= 0; i -= CHUNK_SIZE) {
    const chunk1 = parseInt(num1.substring(i, i + CHUNK_SIZE));
    const chunk2 = parseInt(num2.substring(i, i + CHUNK_SIZE));

    let sum = chunk1 + chunk2 + carry;
    carry = Math.floor(sum / BASE);
    sum = sum % BASE;

    // 补齐前导零（除了最高位）
    const sumStr = sum.toString().padStart(CHUNK_SIZE, '0');
    result = sumStr + result;
  }

  if (carry) {
    result = carry + result;
  }

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

// 性能对比
const big1 = '9'.repeat(10000);
const big2 = '1'.repeat(10000);

console.time('逐位');
addStrings(big1, big2);
console.timeEnd('逐位');

console.time('分组');
addStringsOptimized(big1, big2);
console.timeEnd('分组');

2. 大数运算库实现原理

// 简化版大数类
class BigNumber {
  constructor(value) {
    if (typeof value === 'string') {
      this.digits = value.replace(/^0+/, '').split('').map(Number).reverse();
    } else if (Array.isArray(value)) {
      this.digits = [...value];
    } else {
      this.digits = String(value).split('').map(Number).reverse();
    }
    this.normalize();
  }

  normalize() {
    // 移除前导零
    while (this.digits.length > 1 && this.digits[this.digits.length - 1] === 0) {
      this.digits.pop();
    }
  }

  toString() {
    return this.digits.slice().reverse().join('');
  }

  add(other) {
    other = other instanceof BigNumber ? other : new BigNumber(other);

    const result = [];
    let carry = 0;
    const maxLen = Math.max(this.digits.length, other.digits.length);

    for (let i = 0; i < maxLen || carry; i++) {
      const a = this.digits[i] || 0;
      const b = other.digits[i] || 0;
      const sum = a + b + carry;

      result.push(sum % 10);
      carry = Math.floor(sum / 10);
    }

    return new BigNumber(result);
  }

  multiply(other) {
    other = other instanceof BigNumber ? other : new BigNumber(other);

    const result = new Array(this.digits.length + other.digits.length).fill(0);

    for (let i = 0; i < this.digits.length; i++) {
      for (let j = 0; j < other.digits.length; j++) {
        result[i + j] += this.digits[i] * other.digits[j];
      }
    }

    // 处理进位
    let carry = 0;
    for (let i = 0; i < result.length; i++) {
      const sum = result[i] + carry;
      result[i] = sum % 10;
      carry = Math.floor(sum / 10);
    }

    return new BigNumber(result);
  }
}

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

最佳实践

1. 实际应用场景

// 1. 财务计算（金额精确计算）
function addCurrency(amount1, amount2) {
  // 转换为分（整数）再计算
  const cents1 = Math.round(parseFloat(amount1) * 100);
  const cents2 = Math.round(parseFloat(amount2) * 100);
  const totalCents = cents1 + cents2;
  return (totalCents / 100).toFixed(2);
}

// 更精确的方案：使用字符串计算
function addCurrencyPrecise(amount1, amount2) {
  // 移除小数点，按整数计算
  const [int1, dec1 = ''] = amount1.split('.');
  const [int2, dec2 = ''] = amount2.split('.');

  // 统一小数位数
  const maxDecimals = Math.max(dec1.length, dec2.length);
  const full1 = int1 + dec1.padEnd(maxDecimals, '0');
  const full2 = int2 + dec2.padEnd(maxDecimals, '0');

  const sum = addStrings(full1, full2);

  // 还原小数点
  const intPart = sum.slice(0, -maxDecimals) || '0';
  const decPart = sum.slice(-maxDecimals).padStart(maxDecimals, '0');
  return `${intPart}.${decPart}`;
}

console.log(addCurrencyPrecise('123.45', '67.89')); // '191.34'

// 2. 大数 ID 生成
function generateBigId() {
  const timestamp = Date.now().toString();
  const random = Math.floor(Math.random() * 10000).toString().padStart(4, '0');
  return timestamp + random;
}

// 3. 区块链相关计算
function calculateHashInput(data) {
  // 处理大数值的哈希计算
  const bigValue = data.value.toString();
  const bigNonce = data.nonce.toString();
  return bigAdd(bigValue, bigNonce);
}

2. 使用 BigInt（推荐）

// ES2020 BigInt
const a = 123456789012345678901234567890n;
const b = 987654321098765432109876543210n;

// 基本运算
console.log(a + b);
console.log(a - b);
console.log(a * b);
console.log(a / b);    // 整除
console.log(a % b);

// 比较
console.log(a > b);
console.log(a === b);

// 注意：不能混合使用 Number 和 BigInt
// console.log(a + 1); // TypeError
console.log(a + 1n); // OK

// 转换
console.log(Number(a)); // 可能丢失精度
console.log(a.toString()); // 推荐

// 从字符串创建
const fromString = BigInt('123456789012345678901234567890');

// 判断是否为 BigInt
console.log(typeof a === 'bigint'); // true

// 边界情况
console.log(1n / 2n); // 0n (整除)
console.log(1n % 2n); // 1n

3. 第三方库

// decimal.js - 高精度小数
import Decimal from 'decimal.js';

const a = new Decimal('0.1');
const b = new Decimal('0.2');
console.log(a.plus(b).toString()); // '0.3'

// bignumber.js - 大数运算
import BigNumber from 'bignumber.js';

const x = new BigNumber('12345678901234567890');
const y = new BigNumber('98765432109876543210');
console.log(x.plus(y).toString());

// 链式调用
const result = new BigNumber(0.1)
  .plus(0.2)
  .times(10)
  .dividedBy(3)
  .toFixed(2);
console.log(result); // '1.00'

4. 性能优化

// 1. 预分配数组空间
function addOptimized(a, b) {
  const maxLen = Math.max(a.length, b.length);
  const result = new Array(maxLen + 1); // 预分配
  let carry = 0;
  let i = a.length - 1;
  let j = b.length - 1;
  let k = maxLen;

  while (i >= 0 || j >= 0 || carry) {
    const sum = (i >= 0 ? a[i--] - '0' : 0) +
                (j >= 0 ? b[j--] - '0' : 0) +
                carry;
    result[k--] = String(sum % 10);
    carry = sum > 9 ? 1 : 0;
  }

  return result.slice(k + 1).join('');
}

// 2. 使用 TypedArray（对于特大数据）
function addWithTypedArray(a, b) {
  const len = Math.max(a.length, b.length);
  const result = new Uint8Array(len + 1);
  let carry = 0;

  for (let i = 0; i < len; i++) {
    const ai = a.length - 1 - i;
    const bi = b.length - 1 - i;
    const digitA = ai >= 0 ? a.charCodeAt(ai) - 48 : 0;
    const digitB = bi >= 0 ? b.charCodeAt(bi) - 48 : 0;

    const sum = digitA + digitB + carry;
    result[len - i] = sum % 10;
    carry = sum > 9 ? 1 : 0;
  }

  if (carry) {
    result[0] = 1;
    return String.fromCharCode(...result.map(d => d + 48));
  }

  return String.fromCharCode(...result.slice(1).map(d => d + 48));
}

面试要点

1. 精度问题原因：JavaScript 使用 IEEE 754 双精度浮点数，最大安全整数为 2^53 - 1
2. 解决方案：字符串逐位相加、BigInt、第三方库
3. 算法核心：模拟竖式加法，从低位到高位，处理进位
4. 优化方向：分组处理、预分配内存、TypedArray
5. 实际应用：财务计算、区块链、大数 ID

常见面试题

// 面试题 1：实现大数相加
function addStrings(num1, num2) {
  let result = '';
  let carry = 0;
  let i = num1.length - 1;
  let j = num2.length - 1;

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

  return result;
}

// 面试题 2：实现大数相乘
function multiplyStrings(num1, num2) {
  if (num1 === '0' || num2 === '0') return '0';

  const result = new Array(num1.length + num2.length).fill(0);

  for (let i = num1.length - 1; i >= 0; i--) {
    for (let j = num2.length - 1; j >= 0; j--) {
      const product = (num1[i] - '0') * (num2[j] - '0');
      const sum = product + result[i + j + 1];

      result[i + j + 1] = sum % 10;
      result[i + j] += Math.floor(sum / 10);
    }
  }

  // 移除前导零
  let i = 0;
  while (i < result.length && result[i] === 0) i++;

  return result.slice(i).join('');
}

// 面试题 3：为什么 0.1 + 0.2 !== 0.3？
// 0.1 和 0.2 在二进制中是无限循环小数
// 存储时会被截断，导致精度丢失
// 解决方案：使用整数运算或 toFixed

// 面试题 4：如何比较两个大数的大小？
function compareBig(a, b) {
  a = a.replace(/^0+/, '');
  b = b.replace(/^0+/, '');

  if (a.length !== b.length) {
    return a.length > b.length ? 1 : -1;
  }

  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      return a[i] > b[i] ? 1 : -1;
    }
  }

  return 0;
}

// 面试题 5：实现大数阶乘
function factorial(n) {
  if (n <= 1) return '1';

  let result = '1';
  for (let i = 2; i <= n; i++) {
    result = multiplyStrings(result, String(i));
  }

  return result;
}

console.log(factorial(100));
// 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000