加算演算子だけを使用して、減算・乗算・除算を実装する

今回解いた問題

「加算演算子(+)だけを使用して、減算・乗算・除算を実装せよ」

『世界で闘うプログラミング力を鍛える150問　トップIT企業のプログラマになるための本 』を解いている際に見つけた問題を解いてみました。
以前LeetCodeでも似たような問題を解いた気がしたんですが、ちょっと探してみても見つけられず…。

今回はC++でコードを書いてみます。演算の対象となる値はint型、答えもint型と仮定します。

目次

符号反転の関数

後ほど何かと使用するので、まずは符号を反転させる関数を書いてしまいます。
int型では、マイナスの値は2の補数で表現されているので、ビット反転させて1を足せば符号が反転します。

int reverse_sign(int n) {
    return ~n + 1;
}

減算

符号が反転できれば、減算は単純です。 を と考えてあげればいいのです。
ただし、少し注意が必要なのがオーバーフローです。bがINT_MINの場合は、符号を反転させるとオーバーフローを起こしてしまうので、この場合だけaとbをうまいことずらしてあげてオーバーフローを防ぐ必要があります。コード中では、 と書き換えてオーバーフローを防いでいます。

int substract(int a, int b) {
    // bがINT_MINの場合は符号を逆転させるとオーバーフローするので、1を足してあげる。
    // aがINT_MAXの場合はa+1はオーバーフローするが、その場合はどうせ引き算の結果も
    // オーバーフローするので気にしない。
    if (b == INT_MIN) {
        a += 1;
        b += 1;
    }

    return a + reverse_sign(b);
}

乗算

次は乗算です。aもbも正の値の場合はa + a + ... + a というように、aをb回足したものになります。
負の数乗算の場合は、符号だけ別に考えてあげれば、同じ方法で考えることができます。
乗算でも、オーバーフローするケースがあるので注意が必要です。

int multiply(int a, int b) {
    // 符号を反転させるとオーバーフローしてしまう特殊なケースの処理
    if (((a == 1) && (b == INT_MIN)) || (a == INT_MIN) && (b == 1)) {
        return INT_MIN;
    }

    // 積の符号を持っておく
    bool isPositive = ((a >= 0) == (b >= 0));

    // aとbを両方positiveに
    if (a < 0) { a = reverse_sign(a); }
    if (b < 0) { b = reverse_sign(b); }

    // aをb回足す
    int ans = 0;
    for (int i = 0; i < b; i++) {
        ans += a;
    }

    // 答えの符号を合わせる
    if (!isPositive) {
        ans = reverse_sign(ans);
    }

    return ans;
}

除算

こちらも乗算とほぼ同様です。a/bのaもbもどちらも正の数の場合は、aからbを引けるだけ引いてあげればいいです。負の数が与えられた場合は、乗算と同様正の数に直して割り算した後符号を合わせます。これで、intのキャストと同様に0の方向に丸め込まれた整数が帰ってくるはずです。

オーバーフローの処理は少し面倒くさいです。bだけがINT_MINの場合は常に答えは0となるので問題ないのですが、aだけがINT_MINの場合が厄介です。この場合は、

という変形をしてaの値を少しずらしてあげます。bが正の数であれば、a + bはINT_MINより小さくなるので、オーバーフローは起きなくなります。
bが負の場合は(a + b)はオーバーフローしてしまうので、

という変形でオーバーフローを防ぎます。

ゼロ除算の処理も忘れずに。

int divide(int a, int b) {
    // ゼロ除算の処理
    if (b == 0) { return INT_MAX; }

    // 符号を反転させるとオーバーフローしてしまう特殊なケースの処理
    if ((a == INT_MIN) && (b == INT_MIN)) { return 1; }
    else if (b == INT_MIN) { return 0; }
    else if (a == INT_MIN) {
        if (b >= 0) {
            return substract(divide(a + b, b), 1);
        } else {
            b = reverse_sign(b);
            return reverse_sign(substract(divide(a + b, b), 1));
        }
    }

    // 商の符号を持っておく
    bool isPositive = ((a >= 0) == (b >= 0));

    // aとbを両方positiveに
    if (a < 0) { a = reverse_sign(a); }
    if (b < 0) { b = reverse_sign(b); }

    // aからbを引けるだけ引く
    int ans = 0;
    while (a >= b) {
        a = substract(a, b);
        ans++;
    }

    // 答えの符号を合わせる
    if (!isPositive) {
        ans = reverse_sign(ans);
    }

    return ans;
}

簡単にテスト

いくつかのテストケースをこれらの関数に投げてみます。

    cout << reverse_sign(3) << endl;
    // -3

    cout << substract(10, 15) << endl;
    // -5

    cout << substract(-10, INT_MIN) << endl;
    // 2147483638

    cout << multiply(3, -7) << endl;
    // -21

    cout << divide(-10, 3) << endl;
    // 3

    cout << divide(INT_MIN, -3) << endl;
    // 715827882

    cout << divide(INT_MIN, 3) << endl;
    // -715827882

…よさそうですね。もしかしたら、オーバーフロー周りの処理が甘いところはあるかもしれません。。