DIV CSS 佈局教程網

用 JavaScript 模擬 MIPS 乘法:把每一步都攤在表格上
編輯:關於JavaScript     

計算機組織課程裡的 MIPS 乘法,用紙筆算很痛苦,用程式模擬則能把每一步的中間狀態視覺化。下面這個小工具接受兩個十進位數字,把它們轉成二進位後逐步演算,並把每一輪的乘數、被乘數與乘積都列在表格裡。

<!DOCTYPE html>
<html>
<head>
<title>MIPS MULTIPLICATION SIMULATOR</title>

<script type="text/javascript">
// 把二進位字串拆成單一字元陣列
function StringToNumberArray(Bin) {
  var numberArray = [];
  for (var i = 0; i < Bin.length; i++) {
    numberArray.push(Bin.substring(i, i + 1));
  }
  return numberArray;
}

// 二進位轉十進位
function ConvertToDecimal(Bin) {
  var decimalNumber = 0;
  var numberArray = StringToNumberArray(Bin);
  numberArray.reverse();
  for (var i = 0; i < numberArray.length; i++) {
    decimalNumber += numberArray[i] * Math.pow(2, i);
  }
  return decimalNumber;
}

// 十進位轉二進位
function ConvertToBinary(dec) {
  var bits = [];
  var dividend = dec;
  var remainder = 0;

  while (dividend >= 2) {
    remainder = dividend % 2;
    bits.push(remainder);
    dividend = (dividend - remainder) / 2;
  }
  bits.push(dividend);
  bits.reverse();

  return bits.join("");
}

// 進入點
function Multiply() {
  var firstNumber = document.getElementById("txtFirst").value;
  var secondNumber = document.getElementById("txtSecond").value;

  var multiplier = ConvertToBinary(firstNumber);   // 乘數
  var multiplicant = ConvertToBinary(secondNumber); // 被乘數
  var product = 0;

  AppendToTable(0, "Initial values", multiplier, multiplicant, product);
  multiplicationAlgoritm(multiplier, multiplicant, product, 4);
}

// 核心演算:每一輪檢查乘數最低位、加、右移、左移
function multiplicationAlgoritm(multiplier, multiplicant, product, counter) {
  if (counter > 0) {
    var iteration = 5 - counter;
    var decProduct = ConvertToDecimal(product);
    var decMultiplier = ConvertToDecimal(multiplier);
    var decMultiplicant = ConvertToDecimal(multiplicant);

    // 乘數最低位為 1,就把被乘數加進乘積
    if (Right(multiplier, 1) == "1") {
      decProduct = decProduct + decMultiplicant;
      product = ConvertToBinary(decProduct);
      AppendToTable(iteration, "1a", multiplier, multiplicant, product);
    } else {
      AppendToTable(iteration, 1, multiplier, multiplicant, product);
    }

    // 被乘數左移一位(乘以 2)
    decMultiplicant = ConvertToDecimal(multiplicant);
    decMultiplicant = decMultiplicant << 1;
    multiplicant = ConvertToBinary(decMultiplicant);
    AppendToTable(iteration, 2, multiplier, multiplicant, product);

    // 乘數右移一位(除以 2)
    decMultiplier = ConvertToDecimal(multiplier);
    decMultiplier = decMultiplier >> 1;
    multiplier = ConvertToBinary(decMultiplier);
    AppendToTable(iteration, 3, multiplier, multiplicant, product);

    counter--;
    multiplicationAlgoritm(multiplier, multiplicant, product, counter);
  }
}

// 把一步的狀態寫進表格
function AppendToTable(iteration, step, multiplier, multiplicant, product) {
  var row = document.getElementById("tblResults").insertRow();

  var cell = row.insertCell();
  cell.innerText = iteration;

  cell = row.insertCell();
  cell.innerText = step;

  cell = row.insertCell();
  cell.innerText = multiplier;

  cell = row.insertCell();
  cell.innerText = multiplicant;

  cell = row.insertCell();
  cell.innerText = product;
}

// 清空表格(保留標題列)
function ResetTable() {
  var tbl = document.getElementById("tblResults");
  for (var i = tbl.rows.length; i > 1; i--) {
    tbl.deleteRow(i - 1);
  }
}

// 取字串右邊的第 n 個字元
function Right(str, n) {
  if (n <= 0) return "";
  else if (n > String(str).length) return str;
  else {
    var iLen = String(str).length;
    return String(str).substring(iLen, iLen - n);
  }
}
</script>

<style type="text/css">
.style1 {
  border-collapse: collapse;
  border-style: solid;
  border-width: 1px;
}
.style2 { width: 6px; }
.style4 { color: #3366FF; }
.style5 { color: #0066FF; }
</style>
</head>

<body>
<h3 class="style4">MIPS MULTIPLICATION SIMULATOR</h3>
<hr style="color: #0033CC" />

<table>
  <tr>
    <td class="style5">Multiplier :</td>
    <td><input id="txtFirst" type="text" /></td>
  </tr>
  <tr>
    <td class="style5">Multiplicant :</td>
    <td><input id="txtSecond" type="text" /></td>
  </tr>
  <tr>
    <td align="center" colspan="2">
      <input id="btnMultiply" type="button" value="Multiply"
             onclick="ResetTable();Multiply();" />
    </td>
  </tr>
</table>

<table class="style1" cellpadding="2" cellspacing="2" id="tblResults">
  <tr>
    <td bgcolor="#3366FF">Iteration</td>
    <td bgcolor="#3366FF">Step</td>
    <td bgcolor="#3366FF">Multiplier</td>
    <td bgcolor="#3366FF" class="style2">Multiplicant</td>
    <td bgcolor="#3366FF">Product</td>
  </tr>
</table>
</body>
</html>

演算法在做什么

MIPS 的乘法本質上是「移位相加」,也就是我們小學學的直式乘法,只是改用二進位:從乘數的最低位開始逐位檢查,若該位是 1 就把被乘數累加進乘積;然後被乘數左移一位、乘數右移一位,進入下一輪。重複的次數等於乘數的位元數。

程式裡的 Right(multiplier, 1) 就是取最低位那個字元,判斷是否為 "1";<< 1 與 >> 1 則分別完成左移與右移。表格中的 step 欄位標記 1、1a、2、3,對應的就是「檢查」「加法」「被乘數左移」「乘數右移」這四個階段。

幾個可改進的地方

innerText 的相容性。innerText 在非 IE 瀏覽器上的支援來得較晚,改用 textContent 會更穩妥,也更符合標準。

位元運算的 32 位限制。<< 與 >> 會先把運算元轉成 32 位元整數,所以這個模擬器處理大數時會失真。教學用途沒問題,但別拿它算真實金額。

递归深度。這裡用遞迴實作迴圈,層數固定為 4 所以無妨;若要推廣到任意位元數,改用 while 迴圈更直觀,也避免堆疊風險。

用 innerHTML 清空。ResetTable() 裡逐列刪除可行,但直接 tbl.innerHTML = '<tr>...標題列...</tr>' 往往更快。

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