今回解いた問題
「加算演算子(+)だけを使用して、減算・乗算・除算を実装せよ」
『世界で闘うプログラミング力を鍛える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
…よさそうですね。もしかしたら、オーバーフロー周りの処理が甘いところはあるかもしれません。。