このエントリーをはてなブックマークに追加

TypeScript

プログラマの数学という書籍を読んでいて、下記のような足し算の話が出てきたのでTypeScriptで実装してみた。  

コンピュータは、10進法を2進法に変換し、2進法を使って計算を行い、2進法で得られた計算結果を10進法に変換する

binaryAdd
(出展:プログラマの数学 p.10)

環境

Node.js v10.10.0

実装内容

下記を実装していきます

  • 10進数から2進数への変換
  • 2進数から10進数への変換
  • 2進数の足し算
  • 10進数の足し算(上記をまとめたもの)

10進数から2進数への変換

10進数から2進数への変換は、10進数の値を2で繰り返し割って、余りを逆順で並べれば良い。
余りをリストに前から突っ込みながら最後にくっつけて数値に再度変換する形で実装。 TypeScript(JavaScript)は標準の割り算で商を取得できないので、Math.floorを使っている。

const decimalToBinary = (n: number) => {
  let binaryN = [];

  while (n > 0) {
    binaryN.unshift(n % 2);
    n = Math.floor(n / 2);
  }

  return Number(binaryN.join(''));
}

2進数から10進数への変換

2進数から10進数への変換は、2進数の各桁に2^(桁数-1)をかけたものの和。
受け取った2進数の桁数を取得して、それぞれの桁の値を取得後、2^(桁数-1)をかけた後に足す処理をする形で実装。

const binaryToDecimal = (n: number) => {
  const digits = n.toString().length;
  let decimalN = 0;

  for (let i = digits - 1; i >= 0; i--) {
    let digitN = Math.floor(n / (10 ** i));
    decimalN += digitN * (2 ** i);
    n = Math.floor(n % (10 ** i));
  }
  
  return decimalN;
}

2進数の足し算

これが地味に大変だった・・・。
2進数同士を10進数のように足し算して、その結果を2進数に直すという形で実装。
例えば、111+10=121 => 1001
各桁の値をリストに入れ、個々の値を処理していく形にした。

const addBinary = (n: number, m: number) => {
  let tmpResult = n + m;
  const digits = tmpResult.toString().length;
  let tmpResultList = [];

  for (let i = digits - 1; i >= 0; i--) {
    let digitN = Math.floor(tmpResult / (10 ** i));
    tmpResultList.push(digitN);
    tmpResult = Math.floor(tmpResult % (10 ** i));
  };

  for (let i = digits - 1; i >= 0; i--) {
    if (i === 0){
      if (tmpResultList[i] >= 2) {
        tmpResultList[i] = tmpResultList[i] % 2;
        tmpResultList.unshift(1);
      }
    } else {
      if (tmpResultList[i] >= 2) {
        tmpResultList[i - 1] += 1;
        tmpResultList[i] = tmpResultList[i] % 2;
      };
    };
  };

  return Number(tmpResultList.join(''));
}

10進数の足し算

上記の処理をまとめたのもの。
(2進数の足し算に10進数の足し算を使ってしまっているのが・・・

const addDecimal = (n: number, m: number) => {
  const resultBinary = addBinary(decimalToBinary(n), decimalToBinary(m));

  return binaryToDecimal(resultBinary);
}

実行結果

下記のようなものをテストし、

console.log("0 + 0 =", addDecimal(0, 0));
console.log("0 + 1 =", addDecimal(0, 1));
console.log("1 + 1 =", addDecimal(1, 1));
console.log("12 + 12 =", addDecimal(12, 12));
console.log("21 + 19 =", addDecimal(21, 19));
console.log("299 + 1 =", addDecimal(299, 1));
console.log("7 + 7 =", addDecimal(7, 7));
console.log("218 + 182 =", addDecimal(218, 182)); 

このような結果になったので、一応しっかり実装できたようです。

0 + 0 = 0
0 + 1 = 1
1 + 1 = 2
12 + 12 = 24
21 + 19 = 40
299 + 1 = 300
7 + 7 = 14
218 + 182 = 400

終わりに

なんとなく足し算を実装してみたんですが、思った以上に面倒な処理をしていて人間の繰り上げの概念すごい。あまりTypeScriptらしい書き方ができていない気がするので、もし改善できるところがあればレビューいただけると嬉しいです。
 
 

 

このエントリーをはてなブックマークに追加

© 2018, Udayan28