引き算を使わずに引き算する

というわけで前回の続きになります。今回は引き算を使わずに引き算をしてみましょう。

まずは足し算の時と同様に論理式をそのままコードに起こしてみましょう。現在の桁がどういう論理関係にあるのかと、繰り下がり(ボロー)がどういう論理関係にあるのかに着目すれば簡単です。

int sub(int a, int b)
{
    while (b != 0)
    {
        int c = (~a & b) << 1;
        a ^= b;
        b = c;
    }
    return a;
}

いろいろ問題はあるのですが、実は add() を使えばもっと簡単に書けます。

int sub2(int a, int b)
{
    return add(a, add(~b, 1));
}

算数の基本ですが、引数 b をマイナスにして足せば a - b の引き算になります。上のコードでは b の 2の補数を計算して「b をマイナスにして」います。2の補数は「全ビットを反転して1を足」せば計算できます。上のコードは「1を足す」にも add() を使っているため非常に高価になっています。しかしマシン語レベルなら (Z80 なら INC 命令) 1個で書きますので、本来ならばここまで高価ではありません。

このコードが面白いのは、同じ事をやるにしても異なるアプローチがあり、それぞれに長所・短所・特徴があるという点でしょう。

さて、次回はいよいよ割り算(当初のゴール)にいってみますかね。