読者です 読者をやめる 読者になる 読者になる

今日も窓辺でプログラム

外資系企業勤めのエンジニアが勉強した内容をまとめておくブログ

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

今回解いた問題

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

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

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

符号反転の関数

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

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

減算

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

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) / b - 1
という変形をしてaの値を少しずらしてあげます。bが正の数であれば、a + bはINT_MINより小さくなるので、オーバーフローは起きなくなります。
bが負の場合は(a + b)はオーバーフローしてしまうので、
 a / b = -( (a + (-b)) / (-b) - 1)
という変形でオーバーフローを防ぎます。

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

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

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