yutaponのブログ

javascript界隈の興味あるネタを備忘録的に残しておく場所

半加算器と全加算器で足し算してみた【testem+mocha+chai】

訳あってJavaScriptでのビット演算について調べてたのでその経過を残しておきます。
もっと良いやり方があるに違いないけど、わからない。。


はじめに

やりたいことは、2つの数を足す関数を作ることです。
・・・そんなの簡単!、とはいかなくて、
算術演算子を使わないで頑張ります。
(算術演算子:+, -, *, /, %)


環境構築

作る前にテスト環境を整えます。
前に一度作っているので、今回もそれを流用します。
javascriptでテスト駆動開発 Mocha+expect.js+testem【前編】 - yutaponのブログ

作業ディレクトリに移動して、ソースとテストファイルを作成します。

$ cd path/to/workspace
$ mkdir src   # ソース置き場
$ mkdir spec  # テストファイル置き場
$ npm init    # package.json作る


今回もMochaとtestemを使います。
インストールしていなければインストールしておきます。

$ npm install -g mocha testem


前回はアサーションライブラリにexpect.jsを使いましたが、
今回は何となくChaiを使ってみます。
Home - Chai

$ npm install chai --save-dev


ソースファイルはsrc/add.js, テストファイルはspec/add_spec.jsとして作成します。

$ touch src/add.js spec/add_spec.js


testem.jsonを作成します。
普通はブラウザ上でテストを実行させるのですが、
DOMに関係ないソースなのでmochaコマンドでnode.jsに実行してもらいます。

// @file testem.json
{
  "framework": "mocha",
  "src_files": [
    "src/*.js",
    "spec/*_spec.js"
  ],
  "launchers": {
    "Mocha": {
      "command": "mocha spec/*_spec.js -R tap",
      "protocol": "tap"
    }
  },
  "launch_in_dev": [
    "Mocha"
  ]
}


あとはtestemを実行させます。

$ testem

ソースとテストファイルを編集するたびにテストが走るようになります。


半加算回路

半加算回路とは、XORのことです。
2つの入力のうち、片方がtrueのときのみtrueを返すあれです。
JavaScriptだと ^ (ハット) でXORの演算が行えます。
でも2つの入力のどちらも真のときは桁上げ(carry)が発生するので、
それも考慮しておく必要があります。

まずは src/add.js に関数を作ります。

// @file add.js

/**
 * @class Calc
 */
function Calc() {}

/**
 * 足し算を行う
 * @param  {Number} x
 * @param  {Number} y
 * @return {Number} sum
 */
Calc.prototype.add = function add(x, y) {
  // 実装する
}

/**
 * 半加算器
 * @param  {Boolean} a 入力1
 * @param  {Boolean} b 入力2
 * @return {Object} { s: 出力, c: 桁上げ }
 */
Calc.prototype.halfAdder = function halfAdder(a, b) {
    // 実装する
};

module.exports = Calc;


関数の仕様をなんとなく決めたらテストコードを作成します。

// @file add_spec.js

var chai = require('chai');
var Calc = require('../src/add');

var assert = chai.assert;

describe('Calc::add()', function () {
    var calc = new Calc();

    it('add(1, 1) = 2', function () {
        var result = calc.add(1, 1);
        assert.equal(result, 2);
    });
});

describe('Calc::halfAdder()', function () {
    var calc = new Calc();

    it('0, 0 => { s: 0, c: 0 }', function () {
        var result = calc.halfAdder(0, 0);
        assert.deepEqual(result, { s: 0, c: 0 });
    });
    it('0, 1 => { s: 1, c: 0 }', function () {
        var result = calc.halfAdder(0, 1);
        assert.deepEqual(result, { s: 1, c: 0 });
    });
    it('1, 0 => { s: 1, c: 0 }', function () {
        var result = calc.halfAdder(1, 0);
        assert.deepEqual(result, { s: 1, c: 0 });
    });
    it('1, 1 => { s: 0, c: 1 }', function () {
        var result = calc.halfAdder(1, 1);
        assert.deepEqual(result, { s: 0, c: 1 });
    });
});


保存したらtestemを実行しているターミナルにたくさんのエラーが出ると思います。
TDDでいうREDを確認するフェーズなのでこれで大丈夫です。
では実装してGREENにしていきましょう。

半加算器を実装するとこうなりました。

/**
 * 半加算器
 * @param  {Boolean} a 入力1
 * @param  {Boolean} b 入力2
 * @return {Object} { s: 出力, c: 桁上げ }
 */
Calc.prototype.halfAdder = function halfAdder(a, b) {
    return {
        s : a ^ b,
        c : a & b
    };
};

桁上げが発生する箇所は & (論理積) で検出することができるんですね。
半加算器のテストも無事通ったので正常に動作していることが保証されました。
GREENになることを確認できたので、安心してリファクタリングを行うことが出来るようになります。


全加算器

全加算器は半加算器の桁上げを考慮したものです。
桁上げを考慮するため、入力は3つになります。

テストコードで関数の仕様を決めます。

describe('Calc::fullAdder()', function () {
    var calc = new Calc();

    it('0, 0, 0 => { s: 0, c: 0 }', function () {
        var result = calc.fullAdder(0, 0, 0);
        assert.deepEqual(result, { s: 0, c: 0 });
    });
    it('0, 1, 0 => { s: 1, c: 0 }', function () {
        var result = calc.fullAdder(0, 1, 0);
        assert.deepEqual(result, { s: 1, c: 0 });
    });
    it('1, 0, 0 => { s: 1, c: 0 }', function () {
        var result = calc.fullAdder(1, 0, 0);
        assert.deepEqual(result, { s: 1, c: 0 });
    });
    it('1, 1, 0 => { s: 0, c: 1 }', function () {
        var result = calc.fullAdder(1, 1, 0);
        assert.deepEqual(result, { s: 0, c: 1 });
    });
    it('0, 0, 1 => { s: 1, c: 0 }', function () {
        var result = calc.fullAdder(0, 0, 1);
        assert.deepEqual(result, { s: 1, c: 0 });
    });
    it('0, 1, 1 => { s: 0, c: 1 }', function () {
        var result = calc.fullAdder(0, 1, 1);
        assert.deepEqual(result, { s: 0, c: 1 });
    });
    it('1, 0, 1 => { s: 0, c: 1 }', function () {
        var result = calc.fullAdder(1, 0, 1);
        assert.deepEqual(result, { s: 0, c: 1 });
    });
    it('1, 1, 1 => { s: 1, c: 1 }', function () {
        var result = calc.fullAdder(1, 1, 1);
        assert.deepEqual(result, { s: 1, c: 1 });
    });
});

組み合わせが多いだけで、テストコードだけみると単純な繰り返しです。

この仕様をもとに実装していきます。
実装した結果がこちら。

/**
 * 全加算器
 * @param  {Boolean} a 入力1
 * @param  {Boolean} b 入力2
 * @param  {Boolean} c 桁上げ
 * @return {Object} { s: 出力, c: 桁上げ }
 */
Calc.prototype.fullAdder = function fullAdder(a, b, c) {
    var sum1 = this.halfAdder(a, b);
    var sum2 = this.halfAdder(sum1.s, c);

    return {
        s : sum2.s,
        c : sum1.c | sum2.c
    };
};

全加算器のテストが全てGREENになることが確認できました。


足し算する関数を実装する

まずいくつかテストコードを追加することにしました。

describe('Calc::add()', function () {
    var calc = new Calc();

    it('add(1, 1) = 2', function () {
        var result = calc.add(1, 1);
        assert.equal(result, 2);
    });
    it('add(5, 3) = 8', function () {  // ここから追加
        var result = calc.add(5, 3);
        assert.equal(result, 8);
    });
    it('add(12345, 9876) = 22221', function () {
        var result = calc.add(12345, 9876);
        assert.equal(result, 22221);
    });
    it('add(9, -2) = 7', function () {
        var result = calc.add(9, -2);
        assert.equal(result, 7);
    });
});

エラーが増えたと思うので、これを減らしていきましょう。


解法のアプローチとして次の手順で進めていきます。

  1. 与えられた引数を2進数文字列に変換する
  2. 小さい桁から順に、ビット同士を全加算器にかけていく
  3. 得られた2進数文字列を10進数に戻す

して、実装した結果がこちら。

/**
 * 足し算を行う
 * @param  {Number} x
 * @param  {Number} y
 * @return {Number} sum
 */
Calc.prototype.add = function add(x, y) {
    var result = [],// 加算結果格納用
        binary,     // 加算結果(2進数)
        sum;        // 加算結果(10進数)
    var bitA = ((x.toString(2)).split('')).reverse(); // ビットを格納した配列にする
    var bitB = ((y.toString(2)).split('')).reverse();
    var i,
        len;
    var a,      // 入力1
        b,      // 入力2
        tmp,    // 一時保存
        c;      // 桁上げ

    len = bitA.length > bitB.length ? bitA.length : bitB.length;
    c   = 0;

    // 小さい桁から走査する
    for (i = 0; i < len; i++) {
        a   = bitA[i] ? bitA[i] : 0;
        b   = bitB[i] ? bitB[i] : 0;
        tmp = this.fullAdder(a, b, c);

        result.push(tmp.s);
        c = tmp.c;
    }

    // 最終桁で桁上げが起きてたら追加する
    if (c) {
        result.push(1);
    }

    // 2進数に変換
    binary = (result.reverse()).join('');

    // 10進数に変換
    sum = parseInt(binary, 2);

    return sum;
};


力技ですが、これでほぼできました。
でも、このテストだけ通りません。

it('add(9, -2) = 7', function () {
    var result = calc.add(9, -2);
    assert.equal(result, 7);
});

負数の足し算・・これはもはや減算と言えるのでは。
2の補数を加算すればいいらしいけど、今回はここまで。


おわりに

算術演算子を縛っているのにもかかわらずfor文でインクリメントしてる・・
のでルール的にアウトです・・。
インクリメント程度であればイテレータを実装すればいいので、
まだ、まだ何とかなる。

add関数の中身が肥大化してしまってるので、リファクタリングしないと。
テストコードがあるのでリファクタが怖くない。

ビット演算についていろいろ調べたので微妙にJavaScript力が上がった。
役に立つかは別として。


参考にした記事

404 Blog Not Found:javascript - NANDで何でもやってみよう-1.まずは足し算から
すごく勉強になった。電子工作でも役に立つ時がくるかもしれない。

ビット演算メモ - ボクノス
ビット演算のパターンについてまとめられていて参考になる。

ビット演算子 - JavaScript リダイレクト 1 | MDN
ビット演算の実用的な使い方が載ってる。あとブラウザのコンソールにMozillaの求人が出てくる。