DIV CSS 佈局教程網

JavaScript 大數相加的實作思路
編輯:關於JavaScript     

面試題:寫一個函式處理「大數相加」——所謂大數,是指超出整數、長整數等常規型別表示範圍的數字。實作語言不限。

這題的關鍵不在語法,而在能不能想到「用什麼存」以及「怎麼模擬手算豎式」。

第一步:選對儲存型別

Number 的安全整數上限是 2^53-1(約 9007 兆),超過就會失真。最簡單可行的方案是用字串保存——字串長度理論上沒有上限,而且天生適合逐位元處理。

第二步:手算豎式

確定用字串之後,題目就明朗了:

  1. 比較兩個字串的長度,取較短者為 len。
  2. 從低位開始,對應位相加,同時記錄進位。
  3. 短的處理完後,把進位交給較長字串的剩餘部分繼續處理。

為了讓「從低位開始」變得方便,可以先把字串反轉,這樣索引 0 就是個位。

完整實作

var strAdd = function (srcA, srcB) {
  var i, temp, tempA, tempB, len, lenA, lenB, carry = 0;
  var res = [], arrA = [], arrB = [], cloneArr = [];

  arrA = srcA.split('');
  arrB = srcB.split('');
  arrA.reverse();
  arrB.reverse();

  lenA = arrA.length;
  lenB = arrB.length;
  len = lenA > lenB ? lenB : lenA;

  // 兩邊都有的部分
  for (i = 0; i < len; i++) {
    tempA = parseInt(arrA[i], 10);
    tempB = parseInt(arrB[i], 10);
    temp = tempA + tempB + carry;
    if (temp > 9) {
      res.push(temp - 10);
      carry = 1;
    } else {
      res.push(temp);
      carry = 0;
    }
  }

  // 較長字串的剩餘部分
  cloneArr = lenA > lenB ? arrA : arrB;
  for (; i < cloneArr.length; i++) {
    tempA = parseInt(cloneArr[i], 10);
    temp = tempA + carry;
    if (temp > 9) {
      res.push(temp - 10);
      carry = 1;
    } else {
      res.push(temp);
      carry = 0;
    }
  }

  // 別忘了最高位可能還有進位
  if (carry) res.push(carry);

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

原版少寫了最後那個 if (carry) res.push(carry);,這代表 999 + 1 會得到 000 而不是 1000——這是最容易漏掉的分支,值得特別留意。

可以更好的地方

  • 不必真的 reverse:直接從尾端往前讀索引,可以省掉兩次反轉。
  • 用 charCodeAt 取代 parseInt:s.charCodeAt(i) - 48 比 parseInt 快得多,因為不用解析整段字串。
  • 負數與小數:原版只處理正整數。若要支援負號,需先記錄正負 then 做減法;若要支援小數,需以點號切分整數與小數部分分別處理。

更簡潔的現代寫法

function bigAdd(a, b) {
  var i = a.length - 1, j = b.length - 1, carry = 0, out = [];
  while (i >= 0 || j >= 0 || carry) {
    var sum = carry + (i >= 0 ? +a[i--] : 0) + (j >= 0 ? +b[j--] : 0);
    out.push(sum % 10);
    carry = sum > 9 ? 1 : 0;
  }
  return out.reverse().join('');
}

用一元正號把字元轉數字,並以 while 條件一次涵蓋「兩邊都沒了但還有進位」的情況,就不需要拆成兩個迴圈。

補充:原始面試題其實有提示「用字串保存大數」,難度已經被降低過。若沒有這個提示,能否自行想到,才是真正的篩選點。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved